oj.uz

Submission #749045

# Submission time Handle Problem Language Result Execution time Memory
749045 2023-05-27T09:27:27 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 2712 ms 118640 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

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

int bccCnt;
int depth[500002], bccNum[500002], bccDeg[500002], pushed[500002];
vector<int> vertices;

int checkBCC(int x){
    int ret = depth[x];
    vertices.push_back(x);
    for(auto y: link[x]){
        if(ans[y]) continue;
        if(depth[y]) ret = min(ret, depth[y]);
        else depth[y] = depth[x] + 1, ret = min(ret, checkBCC(y));
    }
    if(ret >= depth[x]){
        int B = ++bccCnt;
        while(1){
            int tmp = vertices.back(); vertices.pop_back();
            bccNum[tmp] = B;
            if(tmp == x) break;
        }
    }
    return ret;
}

void colorBCC(int x, int c, int b){
    vector<int> sumLink = link[x];
    for(auto y: revLink[x]) sumLink.push_back(y);

    ans[x] = c;
//    printf("In ColorBCC: colored %d as %d\n", x, c);
    for(auto y: sumLink){
        if(bccNum[y] != b || ans[y]) continue;
        colorBCC(y, 3-c, b);
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        ex[i] = x, ey[i] = y;
    }

    while(1){
        /// �ڵ� ������ �� ã��
        for(int i=1; i<=n; i++) deg[i] = 0;
        for(int i=1; i<=n; i++) link[i].clear(), revLink[i].clear();
        for(int i=1; i<=m; i++) if(!ans[ex[i]] && !ans[ey[i]]){
            link[ex[i]].push_back(ey[i]);
            revLink[ey[i]].push_back(ex[i]);
            deg[ex[i]]++;
        }

        queue<int> que;
        for(int i=1; i<=n; i++) if(!ans[i] && !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;
//            printf("In queue: colored %d as %d\n", 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]) if(!pushed[y]) pushed[y] = 1, que.push(y);
            }
            for(auto y: revLink[x]){
                deg[y]--;
                if(!ans[y] && !deg[y] && !pushed[y]) pushed[y] = 1, que.push(y);
            }
        }

        /// ��ĥ�� �� �ƴ��� Ȯ��
        bool Done = 1;
        for(int i=1; i<=n; i++) if(!ans[i]) Done = 0;
        if(Done) break;
        bccCnt = 0;
        for(int i=1; i<=n; i++) bccNum[i] = depth[i] = bccDeg[i] = 0;
        vertices.clear();

        for(int i=1; i<=n; i++) if(!ans[i] && !bccNum[i]) depth[i] = 1, checkBCC(i);
        for(int i=1; i<=m; i++) if(!ans[ex[i]] && !ans[ey[i]] && bccNum[ex[i]] != bccNum[ey[i]]) bccDeg[bccNum[ex[i]]]++;

        int bccTarget = -1;
        for(int i=1; i<=bccCnt; i++) if(!bccDeg[i]) bccTarget = i;
        assert(bccTarget != -1);

        int start = -1;
        for(int i=1; i<=n; i++) if(!ans[i] && bccNum[i] == bccTarget) start = i;
        assert(start != -1);

        /// ��ĥ�� �ش�
        colorBCC(start, 1, bccTarget);

        /// �������� �̾��� ����� ��ĥ�� �ش�
        for(int i=1; i<=n; i++) if(bccNum[i] == bccTarget){
            if(ans[i] == 2){
                for(int j: revLink[i]) if(!ans[j]) ans[j] = 1;
                for(int j: link[i]) if(!ans[j]) ans[j] = 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:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 66864 KB Output is correct
2 Correct 203 ms 70924 KB Output is correct
3 Correct 13 ms 23796 KB Output is correct
4 Correct 68 ms 34596 KB Output is correct
5 Correct 126 ms 53736 KB Output is correct
6 Correct 171 ms 58588 KB Output is correct
7 Correct 131 ms 55304 KB Output is correct
8 Correct 193 ms 56844 KB Output is correct
9 Correct 365 ms 61400 KB Output is correct
10 Correct 325 ms 59044 KB Output is correct
11 Correct 375 ms 59048 KB Output is correct
12 Correct 424 ms 54784 KB Output is correct
13 Correct 260 ms 57444 KB Output is correct
14 Correct 272 ms 55816 KB Output is correct
15 Correct 254 ms 55204 KB Output is correct
16 Correct 231 ms 55912 KB Output is correct
17 Correct 75 ms 28912 KB Output is correct
18 Correct 103 ms 34028 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 67704 KB Output is correct
2 Correct 166 ms 56052 KB Output is correct
3 Correct 118 ms 52232 KB Output is correct
4 Correct 373 ms 57212 KB Output is correct
5 Correct 472 ms 61376 KB Output is correct
6 Correct 311 ms 63756 KB Output is correct
7 Correct 488 ms 62300 KB Output is correct
8 Runtime error 2712 ms 118640 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24276 KB Output is correct
2 Correct 15 ms 24148 KB Output is correct
3 Correct 15 ms 24032 KB Output is correct
4 Correct 15 ms 24128 KB Output is correct
5 Correct 17 ms 24200 KB Output is correct
6 Correct 16 ms 24140 KB Output is correct
7 Correct 17 ms 24148 KB Output is correct
8 Correct 57 ms 24184 KB Output is correct
9 Runtime error 36 ms 48240 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 66864 KB Output is correct
2 Correct 203 ms 70924 KB Output is correct
3 Correct 13 ms 23796 KB Output is correct
4 Correct 68 ms 34596 KB Output is correct
5 Correct 126 ms 53736 KB Output is correct
6 Correct 171 ms 58588 KB Output is correct
7 Correct 131 ms 55304 KB Output is correct
8 Correct 193 ms 56844 KB Output is correct
9 Correct 365 ms 61400 KB Output is correct
10 Correct 325 ms 59044 KB Output is correct
11 Correct 375 ms 59048 KB Output is correct
12 Correct 424 ms 54784 KB Output is correct
13 Correct 260 ms 57444 KB Output is correct
14 Correct 272 ms 55816 KB Output is correct
15 Correct 254 ms 55204 KB Output is correct
16 Correct 231 ms 55912 KB Output is correct
17 Correct 75 ms 28912 KB Output is correct
18 Correct 103 ms 34028 KB Output is correct
19 Correct 213 ms 67704 KB Output is correct
20 Correct 166 ms 56052 KB Output is correct
21 Correct 118 ms 52232 KB Output is correct
22 Correct 373 ms 57212 KB Output is correct
23 Correct 472 ms 61376 KB Output is correct
24 Correct 311 ms 63756 KB Output is correct
25 Correct 488 ms 62300 KB Output is correct
26 Runtime error 2712 ms 118640 KB Execution killed with signal 6
27 Halted 0 ms 0 KB -