34372023-02-27 19:20:15k_balintKét csoportcpp14Time limit exceeded 73/100270ms51768 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=3e5+5;

int n;
vector<int> adj[c];
set<int> s;
int col[c];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        int k;
        while(1){
            cin>>k;
            if(!k) break;
            adj[i].push_back(k);
        }
    }

    srand(12432);
    for(int i=1;i<=n;i++){
        col[i]=rand()%2;
    }

    for(int i=1;i<=n;i++){
        int db=0;
        for(int x:adj[i]){
            if(col[i]==col[x]) ++db;
        }
        if(db>=2) s.insert(i);
    }

    while(!s.empty()){
        int cur=*(s.begin());
        s.erase(cur);
        col[cur]^=1;
        for(int x:adj[cur]){
            int db=0;
            for(int y:adj[x]){
                if(col[x]==col[y]) ++db;
            }
            if(db>=2) s.insert(x);
            else s.erase(x);
        }
    }

    int db=0;
    for(int i=1;i<=n;i++){
        if(col[i]) db++;
    }

    cout << db << endl;
    for(int i=1;i<=n;i++){
        if(col[i]) cout << i << ' ';
    }
}
SubtaskSumTestVerdictTimeMemory
base73/100
1Accepted0/08ms16100 KiB
2Accepted0/070ms25812 KiB
3Accepted3/38ms16504 KiB
4Accepted3/38ms16624 KiB
5Accepted3/38ms16836 KiB
6Accepted3/38ms17024 KiB
7Accepted3/38ms17244 KiB
8Accepted2/28ms17452 KiB
9Accepted3/38ms17592 KiB
10Accepted3/39ms17636 KiB
11Accepted3/39ms17592 KiB
12Accepted3/314ms18528 KiB
13Accepted3/314ms18800 KiB
14Accepted3/314ms19068 KiB
15Accepted6/671ms27588 KiB
16Accepted7/778ms28484 KiB
17Accepted7/786ms29120 KiB
18Accepted6/6135ms36864 KiB
19Accepted6/6150ms38548 KiB
20Accepted6/6170ms40256 KiB
21Time limit exceeded0/6202ms46548 KiB
22Time limit exceeded0/7237ms49332 KiB
23Time limit exceeded0/7263ms27180 KiB
24Time limit exceeded0/7270ms51768 KiB