oj.uz

Submission #748927

# Submission time Handle Problem Language Result Execution time Memory
748927 2023-05-27T07:09:11 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 3000 ms 60560 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 185 ms 60548 KB Output is correct
2 Correct 194 ms 60232 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 67 ms 33100 KB Output is correct
5 Correct 121 ms 47392 KB Output is correct
6 Correct 171 ms 50128 KB Output is correct
7 Correct 136 ms 47584 KB Output is correct
8 Correct 178 ms 50120 KB Output is correct
9 Correct 346 ms 54456 KB Output is correct
10 Correct 305 ms 52916 KB Output is correct
11 Correct 425 ms 52104 KB Output is correct
12 Correct 421 ms 48048 KB Output is correct
13 Correct 278 ms 48508 KB Output is correct
14 Correct 266 ms 48712 KB Output is correct
15 Correct 250 ms 48824 KB Output is correct
16 Correct 227 ms 48948 KB Output is correct
17 Correct 59 ms 26828 KB Output is correct
18 Correct 89 ms 29220 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 60560 KB Output is correct
2 Correct 168 ms 50592 KB Output is correct
3 Correct 126 ms 46460 KB Output is correct
4 Correct 356 ms 51520 KB Output is correct
5 Execution timed out 3045 ms 52576 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24180 KB Output is correct
2 Correct 14 ms 24076 KB Output is correct
3 Correct 14 ms 24032 KB Output is correct
4 Correct 15 ms 24056 KB Output is correct
5 Execution timed out 3064 ms 24056 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 60548 KB Output is correct
2 Correct 194 ms 60232 KB Output is correct
3 Correct 11 ms 23764 KB Output is correct
4 Correct 67 ms 33100 KB Output is correct
5 Correct 121 ms 47392 KB Output is correct
6 Correct 171 ms 50128 KB Output is correct
7 Correct 136 ms 47584 KB Output is correct
8 Correct 178 ms 50120 KB Output is correct
9 Correct 346 ms 54456 KB Output is correct
10 Correct 305 ms 52916 KB Output is correct
11 Correct 425 ms 52104 KB Output is correct
12 Correct 421 ms 48048 KB Output is correct
13 Correct 278 ms 48508 KB Output is correct
14 Correct 266 ms 48712 KB Output is correct
15 Correct 250 ms 48824 KB Output is correct
16 Correct 227 ms 48948 KB Output is correct
17 Correct 59 ms 26828 KB Output is correct
18 Correct 89 ms 29220 KB Output is correct
19 Correct 192 ms 60560 KB Output is correct
20 Correct 168 ms 50592 KB Output is correct
21 Correct 126 ms 46460 KB Output is correct
22 Correct 356 ms 51520 KB Output is correct
23 Execution timed out 3045 ms 52576 KB Time limit exceeded
24 Halted 0 ms 0 KB -