oj.uz

Submission #748987

# Submission time Handle Problem Language Result Execution time Memory
748987 2023-05-27T08:45:56 Z 반딧불(#9966) Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 498 ms 65660 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];
bool pushed[500002];

bool tryColor(int x){ /// x�� �� c�� ������ �������� ����
    vector<int> nDeg (deg+1, deg+n+1);
    vector<int> nAns (ans+1, ans+n+1);
    vector<bool> nPushed (ans+1, ans+n+1);

    queue<int> que;
    que.push(x), nPushed[x] = 1;
    while(!que.empty()){
        int x = (int)que.front(); que.pop();
        nAns[x] = 2;
        for(int y: link[x]) if(nAns[y] == 2) nAns[x] = 1;
        for(int y: revLink[x]) if(nAns[y] == 2) nAns[x] = 1;
        if(nAns[x] == 2) for(auto y: link[x]) if(!nPushed[y]) nPushed[y] = 1, que.push(y);
        for(auto y: revLink[x]){
            nDeg[y]--;
            if(!nDeg[y] && !nPushed[y]) nPushed[y] = 1, que.push(y);
        }
    }

    for(int i=1; i<=n; i++){
        if(!nAns[i]) continue;
        if(nAns[i] == 1){
            bool exists = 0;
            for(int y: link[x]) if(nAns[y] != 1) exists = 1;
            if(!exists) return false;
        }
        if(nAns[i] == 2){
            for(int y: link[x]) if(nAns[y] == 2) return false;
            for(int y: revLink[x]) if(nAns[y] == 2) return false;
        }
    }
    return true;
}

void color(int x, int c){
    queue<int> que;
    que.push(x), pushed[x] = 1;
    while(!que.empty()){
        int x = (int)que.front(); que.pop();
        ans[x] = 2;
        for(int y: link[x]) if(ans[y] == 2) ans[x] = 1;
        for(int y: revLink[x]) if(ans[y] == 2) ans[x] = 1;
        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(!deg[y] && !pushed[y]) pushed[y] = 1, que.push(y);
        }
    }
}

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
    /// ���� Ȯ���� �ֵ��� ó���� �ش�
    queue<int> que;
    for(int i=1; i<=n; i++) if(!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;
        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(!deg[y] && !pushed[y]) pushed[y] = 1, que.push(y);
        }
    }

//    for(int i=1; i<=n; i++){
//        if(!ans[i]) while(1);
//        if(ans[i] == 1){
//            bool exists = 0;
//            for(auto y: link[i]) if(ans[y]==2) exists=1;
//            if(!exists) while(1);
//        }
//        else for(auto y: link[i]) if(ans[y]==2) while(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:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 61612 KB Output is correct
2 Correct 211 ms 65660 KB Output is correct
3 Correct 13 ms 23800 KB Output is correct
4 Correct 66 ms 33132 KB Output is correct
5 Correct 122 ms 50380 KB Output is correct
6 Correct 165 ms 52740 KB Output is correct
7 Correct 148 ms 50104 KB Output is correct
8 Correct 195 ms 51748 KB Output is correct
9 Correct 370 ms 56020 KB Output is correct
10 Correct 347 ms 54104 KB Output is correct
11 Correct 395 ms 53496 KB Output is correct
12 Correct 467 ms 49764 KB Output is correct
13 Correct 268 ms 52356 KB Output is correct
14 Correct 303 ms 50592 KB Output is correct
15 Correct 276 ms 49772 KB Output is correct
16 Correct 277 ms 50748 KB Output is correct
17 Correct 62 ms 26828 KB Output is correct
18 Correct 100 ms 30204 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 62580 KB Output is correct
2 Correct 168 ms 51928 KB Output is correct
3 Correct 146 ms 47024 KB Output is correct
4 Correct 398 ms 51812 KB Output is correct
5 Incorrect 498 ms 56224 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 15 ms 24148 KB Output is correct
2 Correct 15 ms 24160 KB Output is correct
3 Correct 14 ms 23988 KB Output is correct
4 Correct 15 ms 24092 KB Output is correct
5 Incorrect 14 ms 23996 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 177 ms 61612 KB Output is correct
2 Correct 211 ms 65660 KB Output is correct
3 Correct 13 ms 23800 KB Output is correct
4 Correct 66 ms 33132 KB Output is correct
5 Correct 122 ms 50380 KB Output is correct
6 Correct 165 ms 52740 KB Output is correct
7 Correct 148 ms 50104 KB Output is correct
8 Correct 195 ms 51748 KB Output is correct
9 Correct 370 ms 56020 KB Output is correct
10 Correct 347 ms 54104 KB Output is correct
11 Correct 395 ms 53496 KB Output is correct
12 Correct 467 ms 49764 KB Output is correct
13 Correct 268 ms 52356 KB Output is correct
14 Correct 303 ms 50592 KB Output is correct
15 Correct 276 ms 49772 KB Output is correct
16 Correct 277 ms 50748 KB Output is correct
17 Correct 62 ms 26828 KB Output is correct
18 Correct 100 ms 30204 KB Output is correct
19 Correct 217 ms 62580 KB Output is correct
20 Correct 168 ms 51928 KB Output is correct
21 Correct 146 ms 47024 KB Output is correct
22 Correct 398 ms 51812 KB Output is correct
23 Incorrect 498 ms 56224 KB For each person outside the committee there should be someone in the committee who they dislike.
24 Halted 0 ms 0 KB -