oj.uz

답안 #749077

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
749077 2023-05-27T09:49:02 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 3000 ms 65728 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];
bool visited[500002];
vector<int> vertices;

int checkBCC(int x){
    int ret = depth[x];
    visited[x] = 1;
    vertices.push_back(x);
    for(auto y: link[x]){
        if(ans[y]) continue;
        if(visited[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] = visited[i] = 0;
        vertices.clear();

        for(int i=1; i<=n; i++) if(!ans[i] && !visited[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){
            assert(ans[i]);
            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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 65728 KB Output is correct
2 Correct 260 ms 65444 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 71 ms 34616 KB Output is correct
5 Correct 124 ms 50916 KB Output is correct
6 Correct 157 ms 56072 KB Output is correct
7 Correct 131 ms 52952 KB Output is correct
8 Correct 184 ms 54988 KB Output is correct
9 Correct 402 ms 59732 KB Output is correct
10 Correct 394 ms 57736 KB Output is correct
11 Correct 412 ms 57632 KB Output is correct
12 Correct 449 ms 52796 KB Output is correct
13 Correct 310 ms 53560 KB Output is correct
14 Correct 249 ms 53620 KB Output is correct
15 Correct 249 ms 53724 KB Output is correct
16 Correct 315 ms 53940 KB Output is correct
17 Correct 73 ms 28620 KB Output is correct
18 Correct 111 ms 33008 KB Output is correct

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 65616 KB Output is correct
2 Correct 205 ms 54788 KB Output is correct
3 Correct 132 ms 51532 KB Output is correct
4 Correct 375 ms 56528 KB Output is correct
5 Correct 481 ms 56912 KB Output is correct
6 Correct 334 ms 61412 KB Output is correct
7 Correct 521 ms 61560 KB Output is correct
8 Execution timed out 3058 ms 58832 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24148 KB Output is correct
2 Correct 14 ms 24124 KB Output is correct
3 Correct 14 ms 24000 KB Output is correct
4 Correct 14 ms 24088 KB Output is correct
5 Correct 15 ms 24212 KB Output is correct
6 Correct 15 ms 24220 KB Output is correct
7 Correct 21 ms 24196 KB Output is correct
8 Correct 58 ms 24176 KB Output is correct
9 Incorrect 17 ms 23948 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

# 결과 실행 시간 메모리 Grader output
1 Correct 184 ms 65728 KB Output is correct
2 Correct 260 ms 65444 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 71 ms 34616 KB Output is correct
5 Correct 124 ms 50916 KB Output is correct
6 Correct 157 ms 56072 KB Output is correct
7 Correct 131 ms 52952 KB Output is correct
8 Correct 184 ms 54988 KB Output is correct
9 Correct 402 ms 59732 KB Output is correct
10 Correct 394 ms 57736 KB Output is correct
11 Correct 412 ms 57632 KB Output is correct
12 Correct 449 ms 52796 KB Output is correct
13 Correct 310 ms 53560 KB Output is correct
14 Correct 249 ms 53620 KB Output is correct
15 Correct 249 ms 53724 KB Output is correct
16 Correct 315 ms 53940 KB Output is correct
17 Correct 73 ms 28620 KB Output is correct
18 Correct 111 ms 33008 KB Output is correct
19 Correct 224 ms 65616 KB Output is correct
20 Correct 205 ms 54788 KB Output is correct
21 Correct 132 ms 51532 KB Output is correct
22 Correct 375 ms 56528 KB Output is correct
23 Correct 481 ms 56912 KB Output is correct
24 Correct 334 ms 61412 KB Output is correct
25 Correct 521 ms 61560 KB Output is correct
26 Execution timed out 3058 ms 58832 KB Time limit exceeded
27 Halted 0 ms 0 KB -