158292025-03-03 23:56:06oKét csoportcpp17Hibás válasz 38/100300ms16564 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();
RészfeladatÖsszpontTesztVerdiktIdőMemória
base38/100
1Hibás válasz0/01ms316 KiB
2Elfogadva0/0112ms7312 KiB
3Hibás válasz0/31ms316 KiB
4Hibás válasz0/31ms316 KiB
5Hibás válasz0/31ms316 KiB
6Hibás válasz0/31ms316 KiB
7Hibás válasz0/31ms316 KiB
8Hibás válasz0/21ms316 KiB
9Elfogadva3/32ms316 KiB
10Elfogadva3/32ms316 KiB
11Elfogadva3/32ms316 KiB
12Elfogadva3/310ms1040 KiB
13Elfogadva3/313ms1028 KiB
14Elfogadva3/314ms1076 KiB
15Elfogadva6/6112ms7288 KiB
16Elfogadva7/7128ms7332 KiB
17Elfogadva7/7141ms7220 KiB
18Időlimit túllépés0/6233ms14388 KiB
19Időlimit túllépés0/6266ms14208 KiB
20Időlimit túllépés0/6286ms14384 KiB
21Időlimit túllépés0/6300ms16564 KiB
22Időlimit túllépés0/7286ms15160 KiB
23Időlimit túllépés0/7284ms14392 KiB
24Időlimit túllépés0/7284ms14388 KiB