oj.uz

Submission #748923

# Submission time Handle Problem Language Result Execution time Memory
748923 2023-05-27T07:04:05 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
0 / 100
 388 ms 60700 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]) exit(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) exit(3);
    }

    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 187 ms 60700 KB Output is correct
2 Correct 216 ms 60424 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 66 ms 33140 KB Output is correct
5 Correct 121 ms 47512 KB Output is correct
6 Correct 173 ms 50200 KB Output is correct
7 Correct 138 ms 47160 KB Output is correct
8 Correct 194 ms 50196 KB Output is correct
9 Correct 388 ms 54696 KB Output is correct
10 Correct 341 ms 53008 KB Output is correct
11 Runtime error 374 ms 49300 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 199 ms 60600 KB Output is correct
2 Correct 188 ms 50776 KB Output is correct
3 Correct 147 ms 46052 KB Output is correct
4 Runtime error 361 ms 48604 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 24148 KB Output is correct
2 Correct 13 ms 24080 KB Output is correct
3 Correct 13 ms 23920 KB Output is correct
4 Runtime error 14 ms 24020 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 187 ms 60700 KB Output is correct
2 Correct 216 ms 60424 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 66 ms 33140 KB Output is correct
5 Correct 121 ms 47512 KB Output is correct
6 Correct 173 ms 50200 KB Output is correct
7 Correct 138 ms 47160 KB Output is correct
8 Correct 194 ms 50196 KB Output is correct
9 Correct 388 ms 54696 KB Output is correct
10 Correct 341 ms 53008 KB Output is correct
11 Runtime error 374 ms 49300 KB Execution failed because the return code was nonzero
12 Halted 0 ms 0 KB -