oj.uz

Submission #749047

# Submission time Handle Problem Language Result Execution time Memory
749047 2023-05-27T09:28:56 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 2746 ms 65720 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]) 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;
        if(bccTarget == -1) exit(0);
        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 184 ms 65720 KB Output is correct
2 Correct 219 ms 65384 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 65 ms 34636 KB Output is correct
5 Correct 124 ms 50868 KB Output is correct
6 Correct 164 ms 56044 KB Output is correct
7 Correct 135 ms 52832 KB Output is correct
8 Correct 195 ms 54948 KB Output is correct
9 Correct 409 ms 59760 KB Output is correct
10 Correct 329 ms 57736 KB Output is correct
11 Correct 379 ms 57488 KB Output is correct
12 Correct 421 ms 52820 KB Output is correct
13 Correct 264 ms 53484 KB Output is correct
14 Correct 235 ms 53604 KB Output is correct
15 Correct 239 ms 53716 KB Output is correct
16 Correct 222 ms 53848 KB Output is correct
17 Correct 64 ms 28620 KB Output is correct
18 Correct 102 ms 32968 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 65704 KB Output is correct
2 Correct 163 ms 54752 KB Output is correct
3 Correct 125 ms 51700 KB Output is correct
4 Correct 362 ms 56500 KB Output is correct
5 Correct 481 ms 56808 KB Output is correct
6 Correct 353 ms 61068 KB Output is correct
7 Correct 507 ms 61092 KB Output is correct
8 Incorrect 2746 ms 58184 KB Unexpected end of file - int32 expected
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24248 KB Output is correct
2 Correct 14 ms 24148 KB Output is correct
3 Correct 14 ms 24048 KB Output is correct
4 Correct 15 ms 24096 KB Output is correct
5 Correct 16 ms 24224 KB Output is correct
6 Correct 14 ms 24148 KB Output is correct
7 Correct 17 ms 24228 KB Output is correct
8 Correct 55 ms 24156 KB Output is correct
9 Incorrect 15 ms 23896 KB Unexpected end of file - int32 expected
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 65720 KB Output is correct
2 Correct 219 ms 65384 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 65 ms 34636 KB Output is correct
5 Correct 124 ms 50868 KB Output is correct
6 Correct 164 ms 56044 KB Output is correct
7 Correct 135 ms 52832 KB Output is correct
8 Correct 195 ms 54948 KB Output is correct
9 Correct 409 ms 59760 KB Output is correct
10 Correct 329 ms 57736 KB Output is correct
11 Correct 379 ms 57488 KB Output is correct
12 Correct 421 ms 52820 KB Output is correct
13 Correct 264 ms 53484 KB Output is correct
14 Correct 235 ms 53604 KB Output is correct
15 Correct 239 ms 53716 KB Output is correct
16 Correct 222 ms 53848 KB Output is correct
17 Correct 64 ms 28620 KB Output is correct
18 Correct 102 ms 32968 KB Output is correct
19 Correct 185 ms 65704 KB Output is correct
20 Correct 163 ms 54752 KB Output is correct
21 Correct 125 ms 51700 KB Output is correct
22 Correct 362 ms 56500 KB Output is correct
23 Correct 481 ms 56808 KB Output is correct
24 Correct 353 ms 61068 KB Output is correct
25 Correct 507 ms 61092 KB Output is correct
26 Incorrect 2746 ms 58184 KB Unexpected end of file - int32 expected
27 Halted 0 ms 0 KB -