oj.uz

Submission #749069

# Submission time Handle Problem Language Result Execution time Memory
749069 2023-05-27T09:46:11 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 3000 ms 65628 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){
    ans[x] = c;
//    printf("In ColorBCC: colored %d as %d\n", x, c);
    for(auto y: link[x]){
        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;
        if(bccTarget == -1) break;

        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:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 65616 KB Output is correct
2 Correct 206 ms 65396 KB Output is correct
3 Correct 16 ms 23720 KB Output is correct
4 Correct 70 ms 34580 KB Output is correct
5 Correct 147 ms 50856 KB Output is correct
6 Correct 157 ms 55988 KB Output is correct
7 Correct 124 ms 52868 KB Output is correct
8 Correct 182 ms 54968 KB Output is correct
9 Correct 370 ms 59704 KB Output is correct
10 Correct 352 ms 57632 KB Output is correct
11 Correct 438 ms 57488 KB Output is correct
12 Correct 419 ms 52812 KB Output is correct
13 Correct 267 ms 53532 KB Output is correct
14 Correct 242 ms 53708 KB Output is correct
15 Correct 233 ms 53748 KB Output is correct
16 Correct 240 ms 53948 KB Output is correct
17 Correct 87 ms 28580 KB Output is correct
18 Correct 136 ms 32928 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 65628 KB Output is correct
2 Correct 174 ms 54768 KB Output is correct
3 Correct 141 ms 51480 KB Output is correct
4 Correct 364 ms 56552 KB Output is correct
5 Correct 500 ms 56832 KB Output is correct
6 Correct 325 ms 61020 KB Output is correct
7 Correct 556 ms 61088 KB Output is correct
8 Execution timed out 3074 ms 59920 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 24248 KB Output is correct
2 Correct 14 ms 24148 KB Output is correct
3 Correct 14 ms 24088 KB Output is correct
4 Correct 19 ms 24140 KB Output is correct
5 Correct 17 ms 24148 KB Output is correct
6 Correct 17 ms 24224 KB Output is correct
7 Correct 20 ms 24136 KB Output is correct
8 Correct 71 ms 24152 KB Output is correct
9 Incorrect 20 ms 23936 KB For each person outside the committee there should be someone in the committee who they dislike.
10 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 65616 KB Output is correct
2 Correct 206 ms 65396 KB Output is correct
3 Correct 16 ms 23720 KB Output is correct
4 Correct 70 ms 34580 KB Output is correct
5 Correct 147 ms 50856 KB Output is correct
6 Correct 157 ms 55988 KB Output is correct
7 Correct 124 ms 52868 KB Output is correct
8 Correct 182 ms 54968 KB Output is correct
9 Correct 370 ms 59704 KB Output is correct
10 Correct 352 ms 57632 KB Output is correct
11 Correct 438 ms 57488 KB Output is correct
12 Correct 419 ms 52812 KB Output is correct
13 Correct 267 ms 53532 KB Output is correct
14 Correct 242 ms 53708 KB Output is correct
15 Correct 233 ms 53748 KB Output is correct
16 Correct 240 ms 53948 KB Output is correct
17 Correct 87 ms 28580 KB Output is correct
18 Correct 136 ms 32928 KB Output is correct
19 Correct 219 ms 65628 KB Output is correct
20 Correct 174 ms 54768 KB Output is correct
21 Correct 141 ms 51480 KB Output is correct
22 Correct 364 ms 56552 KB Output is correct
23 Correct 500 ms 56832 KB Output is correct
24 Correct 325 ms 61020 KB Output is correct
25 Correct 556 ms 61088 KB Output is correct
26 Execution timed out 3074 ms 59920 KB Time limit exceeded
27 Halted 0 ms 0 KB -