oj.uz

답안 #749056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
749056 2023-05-27T09:36:03 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 2725 ms 117184 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] = pushed[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] && !depth[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] == 0) exit(0);
            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

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 65740 KB Output is correct
2 Correct 234 ms 65336 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 62 ms 34604 KB Output is correct
5 Correct 117 ms 50888 KB Output is correct
6 Correct 162 ms 56016 KB Output is correct
7 Correct 128 ms 52860 KB Output is correct
8 Correct 203 ms 54948 KB Output is correct
9 Correct 366 ms 59788 KB Output is correct
10 Correct 317 ms 57676 KB Output is correct
11 Correct 402 ms 57540 KB Output is correct
12 Correct 459 ms 52816 KB Output is correct
13 Correct 303 ms 53476 KB Output is correct
14 Correct 234 ms 53620 KB Output is correct
15 Correct 226 ms 53804 KB Output is correct
16 Correct 216 ms 53912 KB Output is correct
17 Correct 70 ms 28664 KB Output is correct
18 Correct 104 ms 32992 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 65672 KB Output is correct
2 Correct 163 ms 54748 KB Output is correct
3 Correct 126 ms 51504 KB Output is correct
4 Correct 409 ms 56668 KB Output is correct
5 Correct 477 ms 56808 KB Output is correct
6 Correct 331 ms 61024 KB Output is correct
7 Correct 497 ms 61096 KB Output is correct
8 Runtime error 2725 ms 117184 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24144 KB Output is correct
2 Correct 14 ms 24060 KB Output is correct
3 Correct 15 ms 24032 KB Output is correct
4 Correct 14 ms 24096 KB Output is correct
5 Correct 15 ms 24148 KB Output is correct
6 Correct 15 ms 24228 KB Output is correct
7 Correct 17 ms 24180 KB Output is correct
8 Correct 56 ms 24156 KB Output is correct
9 Runtime error 36 ms 48228 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 65740 KB Output is correct
2 Correct 234 ms 65336 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 62 ms 34604 KB Output is correct
5 Correct 117 ms 50888 KB Output is correct
6 Correct 162 ms 56016 KB Output is correct
7 Correct 128 ms 52860 KB Output is correct
8 Correct 203 ms 54948 KB Output is correct
9 Correct 366 ms 59788 KB Output is correct
10 Correct 317 ms 57676 KB Output is correct
11 Correct 402 ms 57540 KB Output is correct
12 Correct 459 ms 52816 KB Output is correct
13 Correct 303 ms 53476 KB Output is correct
14 Correct 234 ms 53620 KB Output is correct
15 Correct 226 ms 53804 KB Output is correct
16 Correct 216 ms 53912 KB Output is correct
17 Correct 70 ms 28664 KB Output is correct
18 Correct 104 ms 32992 KB Output is correct
19 Correct 185 ms 65672 KB Output is correct
20 Correct 163 ms 54748 KB Output is correct
21 Correct 126 ms 51504 KB Output is correct
22 Correct 409 ms 56668 KB Output is correct
23 Correct 477 ms 56808 KB Output is correct
24 Correct 331 ms 61024 KB Output is correct
25 Correct 497 ms 61096 KB Output is correct
26 Runtime error 2725 ms 117184 KB Execution killed with signal 6
27 Halted 0 ms 0 KB -