oj.uz

Submission #748925

# Submission time Handle Problem Language Result Execution time Memory
748925 2023-05-27T07:06:03 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
0 / 100
 380 ms 60488 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
vector<int> link[500002], revLink[500002];

int ans[500002]; /// 0: ���� �� ��, 1: ��ĥ X, 2: ��ĥ O
vector<int> ansVec;
int sweeper = 1;
int deg[500002];
bool pushed[500002];

bool tryColor(int x){ /// x�� �� c�� ������ �������� ����
    vector<int> nDeg (deg+1, deg+n+1);
    vector<int> nAns (ans+1, ans+n+1);
    vector<bool> nPushed (ans+1, ans+n+1);

    queue<int> que;
    que.push(x), nPushed[x] = 1;
    while(!que.empty()){
        int x = (int)que.front(); que.pop();
        nAns[x] = 2;
        for(int y: link[x]) if(nAns[y] == 2) nAns[x] = 1;
        for(int y: revLink[x]) if(nAns[y] == 2) nAns[x] = 1;
        if(nAns[x] == 2) for(auto y: link[x]) if(!nPushed[y]) nPushed[y] = 1, que.push(y);
        for(auto y: revLink[x]){
            nDeg[y]--;
            if(!nDeg[y] && !nPushed[y]) que.push(y);
        }
    }

    for(int i=1; i<=n; i++){
        if(!nAns[i]) continue;
        if(nAns[i] == 1){
            bool exists = 0;
            for(int y: link[x]) if(nAns[y] != 1) exists = 1;
            if(!exists) return false;
        }
        if(nAns[i] == 2){
            for(int y: link[x]) if(nAns[y] == 2) return false;
            for(int y: revLink[x]) if(nAns[y] == 2) return false;
        }
    }
    return true;
}

void color(int x, int c){
    queue<int> que;
    que.push(x), pushed[x] = 1;
    while(!que.empty()){
        int x = (int)que.front(); que.pop();
        ans[x] = 2;
        for(int y: link[x]) if(ans[y] == 2) ans[x] = 1;
        for(int y: revLink[x]) if(ans[y] == 2) ans[x] = 1;
        if(ans[x] == 2) for(auto y: link[x]) if(!pushed[y]) pushed[y] = 1, que.push(y);
        for(auto y: revLink[x]){
            deg[y]--;
            if(!deg[y] && !pushed[y]) que.push(y);
        }
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        revLink[y].push_back(x);
        deg[x]++;
    }

    /// Algorithm
    /// ���� Ȯ���� �ֵ��� ó���� �ش�
    queue<int> que;
    for(int i=1; i<=n; i++) if(!deg[i]) pushed[i] = 1, que.push(i);
    while(!que.empty()){
        int x = que.front(); que.pop();
        int c = 2;
        for(int y: link[x]) if(ans[y] == 2) c = 1;
        for(int y: revLink[x]) if(ans[y] == 2) c = 1;
        ans[x] = c;
        if(ans[x] == 2) for(auto y: link[x]) if(!pushed[y]) pushed[y] = 1, que.push(y);
        for(auto y: revLink[x]){
            deg[y]--;
            if(!deg[y] && !pushed[y]) que.push(y);
        }
    }

    /// �������� ���� ��� deg > 0
    for(int i=1; i<=n; i++){
        if(ans[i]) continue;
        if(tryColor(i)) color(i, 2);
        else color(i, 1);
    }

    for(int i=1; i<=n; i++){
        if(!ans[i]) while(1);
        if(ans[i] == 1){
            bool exists = 0;
            for(auto y: link[i]) if(ans[y]==2) exists=1;
            if(!exists) exit(2);
        }
        else for(auto y: link[i]) if(ans[y]==2) while(1);
    }

    for(int i=1; i<=n; i++) if(ans[i] == 2) ansVec.push_back(i);
    printf("%d\n", (int)ansVec.size());
    for(auto x: ansVec) printf("%d ", x);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 60464 KB Output is correct
2 Correct 206 ms 60300 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 59 ms 33236 KB Output is correct
5 Correct 119 ms 47432 KB Output is correct
6 Correct 160 ms 50152 KB Output is correct
7 Correct 135 ms 47092 KB Output is correct
8 Correct 176 ms 50032 KB Output is correct
9 Correct 380 ms 54564 KB Output is correct
10 Correct 321 ms 52944 KB Output is correct
11 Runtime error 359 ms 49268 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 60488 KB Output is correct
2 Correct 163 ms 50616 KB Output is correct
3 Correct 122 ms 45956 KB Output is correct
4 Runtime error 361 ms 48612 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24132 KB Output is correct
2 Correct 13 ms 24024 KB Output is correct
3 Correct 13 ms 23944 KB Output is correct
4 Runtime error 14 ms 23968 KB Execution failed because the return code was nonzero
5 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 60464 KB Output is correct
2 Correct 206 ms 60300 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 59 ms 33236 KB Output is correct
5 Correct 119 ms 47432 KB Output is correct
6 Correct 160 ms 50152 KB Output is correct
7 Correct 135 ms 47092 KB Output is correct
8 Correct 176 ms 50032 KB Output is correct
9 Correct 380 ms 54564 KB Output is correct
10 Correct 321 ms 52944 KB Output is correct
11 Runtime error 359 ms 49268 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -