9996 | 2024. 03. 23 18:43:09 | 111 | Két csoport | cpp17 | Futási hiba 41/100 | 197ms | 60300 KiB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
#ifndef ONLINE_JUDGE
freopen("be2.txt","r",stdin);
#endif
int N;
cin>>N;
vector<vector<int>>g(N+1);
for(int i=1;i<=N;i++){
for(int j;cin>>j,j;){
g[i].push_back(j);
}
}
vector<int>v(N+1);
auto dfs1=[&](auto self,int i)->void{
for(int j:g[i]){
if(v[j]){
continue;
}
v[j]=v[i]^3;
self(self,j);
}
};
vector<int>a(N+1);
auto dfs2=[&](auto self,int i)->void{
int c=0;
for(int j:g[i]){
if((a[j]?a[j]:v[j])==v[i]){
c++;
}
}
if(c>1){
a[i]=v[i]^3;
}
else{
a[i]=v[i];
}
for(int j:g[i]){
if(a[j]){
continue;
}
self(self,j);
}
};
for(int i=1;i<=N;i++){
if(v[i]){
continue;
}
v[i]=1;
a[i]=1;
dfs1(dfs1,i);
dfs2(dfs2,i);
}
for(int i=1;i<=N;i++){
int c=0;
for(int j:g[i]){
if(a[j]==a[i]){
c++;
}
}
if(c>1){
exit(1);
}
}
vector<int>ans;
for(int i=1;i<=N;i++){
if(a[i]==1){
ans.push_back(i);
}
}
cout<<ans.size()<<'\n';
for(int i:ans){
cout<<i<<' ';
}
cout<<'\n';
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 41/100 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 59ms | 18448 KiB | |||
3 | Elfogadva | 3/3 | 3ms | 2376 KiB | |||
4 | Elfogadva | 3/3 | 3ms | 2256 KiB | |||
5 | Elfogadva | 3/3 | 3ms | 2252 KiB | |||
6 | Elfogadva | 3/3 | 3ms | 2416 KiB | |||
7 | Elfogadva | 3/3 | 3ms | 2632 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 2856 KiB | |||
9 | Elfogadva | 3/3 | 3ms | 3024 KiB | |||
10 | Futási hiba | 0/3 | 3ms | 3160 KiB | |||
11 | Futási hiba | 0/3 | 3ms | 3304 KiB | |||
12 | Elfogadva | 3/3 | 8ms | 4944 KiB | |||
13 | Futási hiba | 0/3 | 8ms | 4888 KiB | |||
14 | Futási hiba | 0/3 | 8ms | 5240 KiB | |||
15 | Elfogadva | 6/6 | 61ms | 19592 KiB | |||
16 | Futási hiba | 0/7 | 59ms | 18952 KiB | |||
17 | Futási hiba | 0/7 | 64ms | 22248 KiB | |||
18 | Elfogadva | 6/6 | 123ms | 36056 KiB | |||
19 | Futási hiba | 0/6 | 118ms | 34796 KiB | |||
20 | Futási hiba | 0/6 | 131ms | 41300 KiB | |||
21 | Elfogadva | 6/6 | 186ms | 53992 KiB | |||
22 | Futási hiba | 0/7 | 173ms | 50160 KiB | |||
23 | Futási hiba | 0/7 | 197ms | 57592 KiB | |||
24 | Futási hiba | 0/7 | 193ms | 60300 KiB |