oj.uz

Submission #749066

# Submission time Handle Problem Language Result Execution time Memory
749066 2023-05-27T09:42:59 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 2710 ms 65672 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);
        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: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 254 ms 65644 KB Output is correct
2 Correct 195 ms 65440 KB Output is correct
3 Correct 14 ms 23748 KB Output is correct
4 Correct 73 ms 34728 KB Output is correct
5 Correct 118 ms 50848 KB Output is correct
6 Correct 208 ms 55932 KB Output is correct
7 Correct 132 ms 52940 KB Output is correct
8 Correct 189 ms 54940 KB Output is correct
9 Correct 390 ms 59704 KB Output is correct
10 Correct 351 ms 57740 KB Output is correct
11 Correct 401 ms 57492 KB Output is correct
12 Correct 438 ms 52828 KB Output is correct
13 Correct 290 ms 53552 KB Output is correct
14 Correct 266 ms 53704 KB Output is correct
15 Correct 294 ms 53808 KB Output is correct
16 Correct 248 ms 53880 KB Output is correct
17 Correct 77 ms 28620 KB Output is correct
18 Correct 107 ms 32976 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 65672 KB Output is correct
2 Correct 182 ms 54692 KB Output is correct
3 Correct 138 ms 51472 KB Output is correct
4 Correct 360 ms 56508 KB Output is correct
5 Correct 486 ms 56816 KB Output is correct
6 Correct 336 ms 61024 KB Output is correct
7 Correct 473 ms 61088 KB Output is correct
8 Incorrect 2710 ms 60680 KB For each person outside the committee there should be someone in the committee who they dislike.
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24196 KB Output is correct
2 Correct 14 ms 24148 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 15 ms 24136 KB Output is correct
5 Correct 17 ms 24132 KB Output is correct
6 Correct 15 ms 24236 KB Output is correct
7 Correct 17 ms 24148 KB Output is correct
8 Correct 58 ms 24152 KB Output is correct
9 Incorrect 15 ms 23892 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 254 ms 65644 KB Output is correct
2 Correct 195 ms 65440 KB Output is correct
3 Correct 14 ms 23748 KB Output is correct
4 Correct 73 ms 34728 KB Output is correct
5 Correct 118 ms 50848 KB Output is correct
6 Correct 208 ms 55932 KB Output is correct
7 Correct 132 ms 52940 KB Output is correct
8 Correct 189 ms 54940 KB Output is correct
9 Correct 390 ms 59704 KB Output is correct
10 Correct 351 ms 57740 KB Output is correct
11 Correct 401 ms 57492 KB Output is correct
12 Correct 438 ms 52828 KB Output is correct
13 Correct 290 ms 53552 KB Output is correct
14 Correct 266 ms 53704 KB Output is correct
15 Correct 294 ms 53808 KB Output is correct
16 Correct 248 ms 53880 KB Output is correct
17 Correct 77 ms 28620 KB Output is correct
18 Correct 107 ms 32976 KB Output is correct
19 Correct 182 ms 65672 KB Output is correct
20 Correct 182 ms 54692 KB Output is correct
21 Correct 138 ms 51472 KB Output is correct
22 Correct 360 ms 56508 KB Output is correct
23 Correct 486 ms 56816 KB Output is correct
24 Correct 336 ms 61024 KB Output is correct
25 Correct 473 ms 61088 KB Output is correct
26 Incorrect 2710 ms 60680 KB For each person outside the committee there should be someone in the committee who they dislike.
27 Halted 0 ms 0 KB -