158302025-03-03 23:57:20oKét csoportcpp17Wrong answer 62/100216ms21440 KiB
#include <bits/stdc++.h>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin>>n;
  if(n<1000){
    return 0;
  }
  vector<vector<int>>g(n+1);
  for(int i=1;i<=n;i++){
    int a;
    while(cin>>a,a){
      g[i].push_back(a);
      //cout<<i<<' '<<a<<endl;
    }
  }
  vector<int>v(n+1),p(n+1);
  for(int i=1;i<=n;i++){
    if(v[i]){
      continue;
    }
    v[i]=1;
    deque<int>q;
    q.push_back(i);
    while(!q.empty()){
      int a=q.front();
      q.pop_front();
      for(int b:g[a]){
        if(v[b]){
          continue;
        }
        v[b]=v[a]+1;
        p[b]=a;
        q.push_back(b);
      }
    }
  }
  vector<int>ans(n+1,-1);
  for(int i=1;i<=n;i++){
    int c=0;
    for(int j:g[i]){
      if(v[j]==v[i]){
        c++;
      }
    }
    if(c!=2){
      ans[i]=v[i]%2;
    }
  }
  auto dfs=[&](auto f,int i)->void{
    if(ans[i]<0){
      return;
    }
    for(int j:g[i]){
      if(v[j]!=v[i]){
        continue;
      }
      if(ans[j]>=0){
        continue;
      }
      ans[j]=ans[i]^1;
      f(f,j);
    }
  };
  for(int i=1;i<=n;i++){
    dfs(dfs,i);
  }
  for(int i=1;i<=n;i++){
    if(ans[i]>=0){
      continue;
    }
    ans[i]=v[i]%2;
    dfs(dfs,i);
  }
  for(int i=1;i<=n;i++){
    if(ans[i]==v[i]%2){
      continue;
    }
    int a=i;
    int b=i;
    while(a==b){
      b=p[a];
      for(int c:g[b]){
        if(c!=a&&ans[c]==ans[b]){
          ans[b]=v[a]%2;
          a=b;
          break;
        }
      }
    }
  }
  cout<<count(ans.begin(),ans.end(),0)<<endl;
  for(int i=1;i<=n;i++){
    if(ans[i]==0){
      cout<<i<<' ';
    }
  }
  cout<<endl;
  for(int i=1;i<=n;i++){
    int c=0;
    for(int j:g[i]){
      if(ans[j]==ans[i]){
        c++;
      }
    }
    if(c>1){
      return 2;
    }
  }
  return 0;
}

bool test(){
  int T=0;
  while(true){
      T++;
     int n=12;
    stringstream s;
    s<<n<<endl;
    vector<vector<int>>g(n+1);
    for(int i=1;i<=n;i++){
      for(int j=0;j<3;j++){
        int x=rand()%n+1;
        if(x==i){
          j--;
          continue;
        }
        if(g[i].size()==3||g[x].size()==3||count(g[i].begin(),g[i].end(),x))continue;
        g[i].push_back(x);
        g[x].push_back(i);
      }
    }
     for(int i=1;i<=n;i++){
      for(int j:g[i])s<<j<<' ';s<<"0\n";
    }
    //cout<<s.str()<<endl<<endl;
    if(false){
      bool wk=0;
      for(int b=0;b<(1<<n);b++){
          wk=1;
        for(int i=1;i<=n;i++){
        int c=0;
        for(int j:g[i]){
          if((b>>i-1&1)==(b>>j-1&1)){
            c++;
          }
        }
        if(c>=2){
          wk=0;
        }
      }
        if(wk){
        for(int i=1;i<=n;i++)cout<<i<<' '<<(b>>i-1&1)<<endl;
          break;
        }
      }
      cout<<endl<<endl;
      if(!wk)exit(10);
    }
    cin.rdbuf(s.rdbuf());
    stringstream u;
    auto oo=cout.rdbuf(u.rdbuf());
    int res=main();
    cout.rdbuf(oo);
    //cout<<u.str()<<endl;
    if(res){
      cout<<u.str()<<endl;
      cout<<"FAILED "<<T<<endl;
      exit(1);
    }
    else if(T%100==0)cout<<"OK "<<T<<endl;
  }
}

//bool _=test();
SubtaskSumTestVerdictTimeMemory
base62/100
1Wrong answer0/01ms316 KiB
2Accepted0/059ms7220 KiB
3Wrong answer0/31ms316 KiB
4Wrong answer0/31ms508 KiB
5Wrong answer0/31ms316 KiB
6Wrong answer0/31ms316 KiB
7Wrong answer0/31ms316 KiB
8Wrong answer0/21ms316 KiB
9Accepted3/31ms316 KiB
10Accepted3/31ms316 KiB
11Accepted3/32ms316 KiB
12Accepted3/36ms1076 KiB
13Accepted3/37ms1120 KiB
14Accepted3/37ms876 KiB
15Accepted6/657ms7212 KiB
16Accepted7/761ms7204 KiB
17Accepted7/767ms7216 KiB
18Accepted6/6120ms14344 KiB
19Accepted6/6123ms14388 KiB
20Accepted6/6142ms14384 KiB
21Accepted6/6180ms21440 KiB
22Time limit exceeded0/7201ms21352 KiB
23Time limit exceeded0/7207ms21300 KiB
24Time limit exceeded0/7216ms21300 KiB