oj.uz

Submission #748868

# Submission time Handle Problem Language Result Execution time Memory
748868 2023-05-27T05:52:40 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 479 ms 60080 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
vector<int> link[500002], revLink[500002];

int ans[500002]; /// 0: ���� �� ��, 1: ��ĥ X, 2: ��ĥ O
vector<int> ansVec;
int sweeper = 1;
int deg[500002];

void color(int x, int c){
    ans[x] = c;
    for(auto y: link[x]){
        if(ans[y]) continue;
        color(y, 3-c);
    }
}

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(y);
        revLink[y].push_back(x);
        deg[x]++;
    }

    /// Algorithm
    /// A -> B���� B�� O�� A�� X�� ��� ��ĥ, B�� ���� X�� A�� O�� ��ĥ

    queue<int> que;
    for(int i=1; i<=n; i++) if(!deg[i]) 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;
        ans[x] = c;
        for(auto y: revLink[x]){
            deg[y]--;
            if(!deg[y]) que.push(y);
        }
    }

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

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 60012 KB Output is correct
2 Correct 197 ms 59848 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 56 ms 32736 KB Output is correct
5 Correct 122 ms 46916 KB Output is correct
6 Correct 158 ms 49688 KB Output is correct
7 Correct 135 ms 47064 KB Output is correct
8 Correct 177 ms 49664 KB Output is correct
9 Correct 322 ms 53916 KB Output is correct
10 Correct 305 ms 52480 KB Output is correct
11 Correct 361 ms 51792 KB Output is correct
12 Correct 416 ms 47420 KB Output is correct
13 Correct 278 ms 51908 KB Output is correct
14 Correct 261 ms 50152 KB Output is correct
15 Correct 250 ms 49332 KB Output is correct
16 Correct 229 ms 50248 KB Output is correct
17 Correct 65 ms 26800 KB Output is correct
18 Correct 100 ms 30208 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 60080 KB Output is correct
2 Correct 162 ms 50168 KB Output is correct
3 Correct 127 ms 46004 KB Output is correct
4 Correct 352 ms 51168 KB Output is correct
5 Incorrect 479 ms 51120 KB For each person outside the committee there should be someone in the committee who they dislike.
6 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24148 KB Output is correct
2 Correct 14 ms 24084 KB Output is correct
3 Correct 13 ms 24028 KB Output is correct
4 Correct 14 ms 24044 KB Output is correct
5 Incorrect 15 ms 24020 KB For each person outside the committee there should be someone in the committee who they dislike.
6 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 60012 KB Output is correct
2 Correct 197 ms 59848 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 56 ms 32736 KB Output is correct
5 Correct 122 ms 46916 KB Output is correct
6 Correct 158 ms 49688 KB Output is correct
7 Correct 135 ms 47064 KB Output is correct
8 Correct 177 ms 49664 KB Output is correct
9 Correct 322 ms 53916 KB Output is correct
10 Correct 305 ms 52480 KB Output is correct
11 Correct 361 ms 51792 KB Output is correct
12 Correct 416 ms 47420 KB Output is correct
13 Correct 278 ms 51908 KB Output is correct
14 Correct 261 ms 50152 KB Output is correct
15 Correct 250 ms 49332 KB Output is correct
16 Correct 229 ms 50248 KB Output is correct
17 Correct 65 ms 26800 KB Output is correct
18 Correct 100 ms 30208 KB Output is correct
19 Correct 185 ms 60080 KB Output is correct
20 Correct 162 ms 50168 KB Output is correct
21 Correct 127 ms 46004 KB Output is correct
22 Correct 352 ms 51168 KB Output is correct
23 Incorrect 479 ms 51120 KB For each person outside the committee there should be someone in the committee who they dislike.
24 Halted 0 ms 0 KB -