oj.uz

Submission #748928

# Submission time Handle Problem Language Result Execution time Memory
748928 2023-05-27T07:10:11 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 3000 ms 60548 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]) nPushed[y] = 1, 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]) pushed[y] = 1, 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]) pushed[y] = 1, 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) while(1);
//        }
//        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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 60548 KB Output is correct
2 Correct 206 ms 60328 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 67 ms 33204 KB Output is correct
5 Correct 135 ms 47444 KB Output is correct
6 Correct 164 ms 50048 KB Output is correct
7 Correct 140 ms 47544 KB Output is correct
8 Correct 179 ms 50076 KB Output is correct
9 Correct 333 ms 54424 KB Output is correct
10 Correct 305 ms 52924 KB Output is correct
11 Correct 379 ms 52228 KB Output is correct
12 Correct 419 ms 47940 KB Output is correct
13 Correct 295 ms 48420 KB Output is correct
14 Correct 284 ms 48596 KB Output is correct
15 Correct 274 ms 48584 KB Output is correct
16 Correct 270 ms 48824 KB Output is correct
17 Correct 68 ms 26800 KB Output is correct
18 Correct 115 ms 29100 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 60480 KB Output is correct
2 Correct 186 ms 50672 KB Output is correct
3 Correct 145 ms 46404 KB Output is correct
4 Correct 447 ms 51556 KB Output is correct
5 Correct 725 ms 53312 KB Output is correct
6 Correct 1533 ms 51820 KB Output is correct
7 Execution timed out 3027 ms 51468 KB Time limit exceeded
8 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 14 ms 24020 KB Output is correct
3 Correct 13 ms 23932 KB Output is correct
4 Correct 15 ms 24076 KB Output is correct
5 Correct 17 ms 24196 KB Output is correct
6 Correct 15 ms 24020 KB Output is correct
7 Correct 16 ms 24020 KB Output is correct
8 Correct 23 ms 23964 KB Output is correct
9 Correct 14 ms 23764 KB Output is correct
10 Correct 12 ms 23792 KB Output is correct
11 Correct 15 ms 23764 KB Output is correct
12 Runtime error 32 ms 48712 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 60548 KB Output is correct
2 Correct 206 ms 60328 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 67 ms 33204 KB Output is correct
5 Correct 135 ms 47444 KB Output is correct
6 Correct 164 ms 50048 KB Output is correct
7 Correct 140 ms 47544 KB Output is correct
8 Correct 179 ms 50076 KB Output is correct
9 Correct 333 ms 54424 KB Output is correct
10 Correct 305 ms 52924 KB Output is correct
11 Correct 379 ms 52228 KB Output is correct
12 Correct 419 ms 47940 KB Output is correct
13 Correct 295 ms 48420 KB Output is correct
14 Correct 284 ms 48596 KB Output is correct
15 Correct 274 ms 48584 KB Output is correct
16 Correct 270 ms 48824 KB Output is correct
17 Correct 68 ms 26800 KB Output is correct
18 Correct 115 ms 29100 KB Output is correct
19 Correct 229 ms 60480 KB Output is correct
20 Correct 186 ms 50672 KB Output is correct
21 Correct 145 ms 46404 KB Output is correct
22 Correct 447 ms 51556 KB Output is correct
23 Correct 725 ms 53312 KB Output is correct
24 Correct 1533 ms 51820 KB Output is correct
25 Execution timed out 3027 ms 51468 KB Time limit exceeded
26 Halted 0 ms 0 KB -