oj.uz

Submission #748990

# Submission time Handle Problem Language Result Execution time Memory
748990 2023-05-27T08:47:13 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 421 ms 121268 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(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]){
                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 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:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 65668 KB Output is correct
2 Correct 190 ms 65420 KB Output is correct
3 Correct 13 ms 23748 KB Output is correct
4 Correct 69 ms 34560 KB Output is correct
5 Correct 117 ms 50856 KB Output is correct
6 Correct 163 ms 56024 KB Output is correct
7 Correct 129 ms 52924 KB Output is correct
8 Correct 172 ms 54904 KB Output is correct
9 Correct 322 ms 59712 KB Output is correct
10 Correct 316 ms 57812 KB Output is correct
11 Correct 366 ms 57004 KB Output is correct
12 Correct 414 ms 52708 KB Output is correct
13 Correct 243 ms 53504 KB Output is correct
14 Correct 293 ms 53688 KB Output is correct
15 Correct 257 ms 53408 KB Output is correct
16 Correct 235 ms 53884 KB Output is correct
17 Correct 64 ms 28596 KB Output is correct
18 Correct 100 ms 32980 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 65720 KB Output is correct
2 Correct 173 ms 54740 KB Output is correct
3 Correct 118 ms 51676 KB Output is correct
4 Correct 347 ms 56524 KB Output is correct
5 Runtime error 421 ms 121268 KB Execution killed with signal 6
6 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 15 ms 24100 KB Output is correct
4 Correct 15 ms 24120 KB Output is correct
5 Runtime error 34 ms 48776 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 65668 KB Output is correct
2 Correct 190 ms 65420 KB Output is correct
3 Correct 13 ms 23748 KB Output is correct
4 Correct 69 ms 34560 KB Output is correct
5 Correct 117 ms 50856 KB Output is correct
6 Correct 163 ms 56024 KB Output is correct
7 Correct 129 ms 52924 KB Output is correct
8 Correct 172 ms 54904 KB Output is correct
9 Correct 322 ms 59712 KB Output is correct
10 Correct 316 ms 57812 KB Output is correct
11 Correct 366 ms 57004 KB Output is correct
12 Correct 414 ms 52708 KB Output is correct
13 Correct 243 ms 53504 KB Output is correct
14 Correct 293 ms 53688 KB Output is correct
15 Correct 257 ms 53408 KB Output is correct
16 Correct 235 ms 53884 KB Output is correct
17 Correct 64 ms 28596 KB Output is correct
18 Correct 100 ms 32980 KB Output is correct
19 Correct 172 ms 65720 KB Output is correct
20 Correct 173 ms 54740 KB Output is correct
21 Correct 118 ms 51676 KB Output is correct
22 Correct 347 ms 56524 KB Output is correct
23 Runtime error 421 ms 121268 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -