oj.uz

Submission #749002

# Submission time Handle Problem Language Result Execution time Memory
749002 2023-05-27T08:57:53 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 3000 ms 67680 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]) 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;

        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]]++;
        }

        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 176 ms 66856 KB Output is correct
2 Correct 244 ms 67456 KB Output is correct
3 Correct 17 ms 23764 KB Output is correct
4 Correct 68 ms 34588 KB Output is correct
5 Correct 130 ms 53012 KB Output is correct
6 Correct 188 ms 58204 KB Output is correct
7 Correct 136 ms 55028 KB Output is correct
8 Correct 217 ms 56772 KB Output is correct
9 Correct 362 ms 61372 KB Output is correct
10 Correct 300 ms 58960 KB Output is correct
11 Correct 371 ms 58964 KB Output is correct
12 Correct 400 ms 54724 KB Output is correct
13 Correct 258 ms 55672 KB Output is correct
14 Correct 243 ms 55756 KB Output is correct
15 Correct 243 ms 55020 KB Output is correct
16 Correct 235 ms 55972 KB Output is correct
17 Correct 80 ms 28808 KB Output is correct
18 Correct 119 ms 34152 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 67680 KB Output is correct
2 Correct 158 ms 55996 KB Output is correct
3 Correct 129 ms 52176 KB Output is correct
4 Correct 410 ms 56900 KB Output is correct
5 Correct 452 ms 58980 KB Output is correct
6 Correct 315 ms 63224 KB Output is correct
7 Correct 598 ms 62288 KB Output is correct
8 Execution timed out 3034 ms 59772 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24276 KB Output is correct
2 Correct 14 ms 24060 KB Output is correct
3 Correct 13 ms 24020 KB Output is correct
4 Correct 16 ms 24076 KB Output is correct
5 Correct 14 ms 24184 KB Output is correct
6 Correct 15 ms 24148 KB Output is correct
7 Correct 19 ms 24252 KB Output is correct
8 Correct 77 ms 24176 KB Output is correct
9 Runtime error 35 ms 48388 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 176 ms 66856 KB Output is correct
2 Correct 244 ms 67456 KB Output is correct
3 Correct 17 ms 23764 KB Output is correct
4 Correct 68 ms 34588 KB Output is correct
5 Correct 130 ms 53012 KB Output is correct
6 Correct 188 ms 58204 KB Output is correct
7 Correct 136 ms 55028 KB Output is correct
8 Correct 217 ms 56772 KB Output is correct
9 Correct 362 ms 61372 KB Output is correct
10 Correct 300 ms 58960 KB Output is correct
11 Correct 371 ms 58964 KB Output is correct
12 Correct 400 ms 54724 KB Output is correct
13 Correct 258 ms 55672 KB Output is correct
14 Correct 243 ms 55756 KB Output is correct
15 Correct 243 ms 55020 KB Output is correct
16 Correct 235 ms 55972 KB Output is correct
17 Correct 80 ms 28808 KB Output is correct
18 Correct 119 ms 34152 KB Output is correct
19 Correct 200 ms 67680 KB Output is correct
20 Correct 158 ms 55996 KB Output is correct
21 Correct 129 ms 52176 KB Output is correct
22 Correct 410 ms 56900 KB Output is correct
23 Correct 452 ms 58980 KB Output is correct
24 Correct 315 ms 63224 KB Output is correct
25 Correct 598 ms 62288 KB Output is correct
26 Execution timed out 3034 ms 59772 KB Time limit exceeded
27 Halted 0 ms 0 KB -