oj.uz

Submission #749062

# Submission time Handle Problem Language Result Execution time Memory
749062 2023-05-27T09:41:34 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 3000 ms 65724 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);
        if(!vertices.empty()) exit(0);
        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 183 ms 65696 KB Output is correct
2 Correct 200 ms 65632 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 67 ms 34536 KB Output is correct
5 Correct 115 ms 50916 KB Output is correct
6 Correct 155 ms 56008 KB Output is correct
7 Correct 152 ms 52860 KB Output is correct
8 Correct 172 ms 54888 KB Output is correct
9 Correct 344 ms 59712 KB Output is correct
10 Correct 312 ms 57732 KB Output is correct
11 Correct 361 ms 57536 KB Output is correct
12 Correct 416 ms 52796 KB Output is correct
13 Correct 262 ms 53492 KB Output is correct
14 Correct 242 ms 53692 KB Output is correct
15 Correct 232 ms 53744 KB Output is correct
16 Correct 217 ms 53880 KB Output is correct
17 Correct 63 ms 28684 KB Output is correct
18 Correct 101 ms 32988 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 65724 KB Output is correct
2 Correct 159 ms 54756 KB Output is correct
3 Correct 132 ms 51668 KB Output is correct
4 Correct 359 ms 56492 KB Output is correct
5 Correct 463 ms 56852 KB Output is correct
6 Correct 315 ms 61000 KB Output is correct
7 Correct 489 ms 61284 KB Output is correct
8 Execution timed out 3056 ms 58212 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24148 KB Output is correct
2 Correct 15 ms 24148 KB Output is correct
3 Correct 14 ms 24100 KB Output is correct
4 Correct 15 ms 24160 KB Output is correct
5 Correct 15 ms 24148 KB Output is correct
6 Correct 16 ms 24148 KB Output is correct
7 Correct 18 ms 24172 KB Output is correct
8 Correct 60 ms 24160 KB Output is correct
9 Runtime error 37 ms 48356 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 183 ms 65696 KB Output is correct
2 Correct 200 ms 65632 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 67 ms 34536 KB Output is correct
5 Correct 115 ms 50916 KB Output is correct
6 Correct 155 ms 56008 KB Output is correct
7 Correct 152 ms 52860 KB Output is correct
8 Correct 172 ms 54888 KB Output is correct
9 Correct 344 ms 59712 KB Output is correct
10 Correct 312 ms 57732 KB Output is correct
11 Correct 361 ms 57536 KB Output is correct
12 Correct 416 ms 52796 KB Output is correct
13 Correct 262 ms 53492 KB Output is correct
14 Correct 242 ms 53692 KB Output is correct
15 Correct 232 ms 53744 KB Output is correct
16 Correct 217 ms 53880 KB Output is correct
17 Correct 63 ms 28684 KB Output is correct
18 Correct 101 ms 32988 KB Output is correct
19 Correct 189 ms 65724 KB Output is correct
20 Correct 159 ms 54756 KB Output is correct
21 Correct 132 ms 51668 KB Output is correct
22 Correct 359 ms 56492 KB Output is correct
23 Correct 463 ms 56852 KB Output is correct
24 Correct 315 ms 61000 KB Output is correct
25 Correct 489 ms 61284 KB Output is correct
26 Execution timed out 3056 ms 58212 KB Time limit exceeded
27 Halted 0 ms 0 KB -