9993 | 2024. 03. 23 18:18:38 | 111 | Két csoport | cpp17 | Futási hiba 33/100 | 231ms | 61648 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{
vector<pair<int,int>>w;
for(int j:g[i]){
if(a[j]){
continue;
}
int c=0;
for(int k:g[j]){
if(v[k]!=v[j]){
c++;
}
}
w.emplace_back(c,j);
}
sort(w.begin(),w.end(),greater<>());
for(auto[c,j]:w){
if(a[j]){
continue;
}
a[j]=a[i]^3;
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 | 33/100 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1864 KiB | |||
2 | Elfogadva | 0/0 | 65ms | 18456 KiB | |||
3 | Elfogadva | 3/3 | 3ms | 2228 KiB | |||
4 | Elfogadva | 3/3 | 3ms | 2440 KiB | |||
5 | Elfogadva | 3/3 | 3ms | 2524 KiB | |||
6 | Elfogadva | 3/3 | 3ms | 2528 KiB | |||
7 | Elfogadva | 3/3 | 3ms | 2556 KiB | |||
8 | Futási hiba | 0/2 | 3ms | 2648 KiB | |||
9 | Elfogadva | 3/3 | 3ms | 3064 KiB | |||
10 | Futási hiba | 0/3 | 3ms | 3108 KiB | |||
11 | Futási hiba | 0/3 | 3ms | 3308 KiB | |||
12 | Elfogadva | 3/3 | 8ms | 4844 KiB | |||
13 | Futási hiba | 0/3 | 8ms | 4864 KiB | |||
14 | Futási hiba | 0/3 | 9ms | 5540 KiB | |||
15 | Elfogadva | 6/6 | 65ms | 20000 KiB | |||
16 | Futási hiba | 0/7 | 65ms | 19520 KiB | |||
17 | Futási hiba | 0/7 | 75ms | 23020 KiB | |||
18 | Elfogadva | 6/6 | 133ms | 36220 KiB | |||
19 | Futási hiba | 0/6 | 134ms | 35080 KiB | |||
20 | Futási hiba | 0/6 | 156ms | 49096 KiB | |||
21 | Időlimit túllépés | 0/6 | 201ms | 53576 KiB | |||
22 | Időlimit túllépés | 0/7 | 202ms | 50344 KiB | |||
23 | Időlimit túllépés | 0/7 | 230ms | 57848 KiB | |||
24 | Időlimit túllépés | 0/7 | 231ms | 61648 KiB |