34382023-02-27 19:25:10k_balintKét csoportcpp14Időlimit túllépés 86/100203ms40840 KiB
#include <bits/stdc++.h>
using namespace std;
const int c=3e5+5;

int n;
vector<int> adj[c];
int col[c];
bool rossz[c];
queue<int> q;

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) q.push(i);
    }

    while(!q.empty()){
        int cur=q.front();
        q.pop();

        int db=0;
        for(int x:adj[cur]){
            if(col[cur]==col[x]) ++db;
        }

        if(db<2) continue;

        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) q.push(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 << ' ';
    }
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base86/100
1Elfogadva0/08ms15904 KiB
2Elfogadva0/061ms23500 KiB
3Elfogadva3/38ms16440 KiB
4Elfogadva3/37ms16644 KiB
5Elfogadva3/38ms16868 KiB
6Elfogadva3/38ms16952 KiB
7Elfogadva3/37ms17032 KiB
8Elfogadva2/28ms17168 KiB
9Elfogadva3/38ms17528 KiB
10Elfogadva3/38ms17736 KiB
11Elfogadva3/38ms17952 KiB
12Elfogadva3/313ms18608 KiB
13Elfogadva3/314ms18872 KiB
14Elfogadva3/314ms18940 KiB
15Elfogadva6/661ms25648 KiB
16Elfogadva7/764ms25780 KiB
17Elfogadva7/771ms25768 KiB
18Elfogadva6/6115ms32768 KiB
19Elfogadva6/6123ms32928 KiB
20Elfogadva6/6136ms33136 KiB
21Elfogadva6/6170ms40136 KiB
22Elfogadva7/7180ms40616 KiB
23Időlimit túllépés0/7203ms40840 KiB
24Időlimit túllépés0/7203ms40828 KiB