oj.uz

Submission #960244

# Submission time Handle Problem Language Result Execution time Memory
960244 2024-04-10T01:37:22 Z Darren0724 Povjerenstvo (COI22_povjerenstvo) C++17
13 / 100
 243 ms 39600 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
//#define int long long
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=500005;
int n,m;
vector<int> vis(N,-1),out(N,0);
vector<int> adj[N];
int32_t main() {
    LCBorz;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;cin>>a>>b;
        out[a]++;
        adj[b].push_back(a);
    }
    vector<int> ans1(N,-1);
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(out[i]==0){
            ans1[i]=1;
            q.push(i);
        }
    }
    auto run=[&]()->void {
        while(q.size()){
            int p=q.front();
            q.pop();
            ans1[p]=1;
            for(int j:adj[p]){
                /*if(ans1[j]==1){
                    cout<<-1<<endl;
                    exit(0);
                }*/
                if(ans1[j]==-1){
                    for(int j1:adj[j]){
                        out[j1]--;
                        if(out[j1]==0){
                            q.push(j1);
                        }
                    }
                }
                ans1[j]=0;
            }
        }
    };
    run();
    for(int i=1;i<=n;i++){
        if(ans1[i]==-1){
            q.push(i);
            run();
        }
    }
    vector<int> ans;
    for(int i=1;i<=n;i++){
        if(ans1[i]==1){
            ans.push_back(i);
        }
    }
    cout<<ans.size()<<endl;
    for(int j:ans){
        cout<<j<<' ';
    }
    cout<<endl;
    
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 35536 KB Output is correct
2 Correct 104 ms 35480 KB Output is correct
3 Correct 8 ms 18008 KB Output is correct
4 Correct 40 ms 25148 KB Output is correct
5 Correct 65 ms 29520 KB Output is correct
6 Correct 101 ms 39148 KB Output is correct
7 Correct 58 ms 19892 KB Output is correct
8 Correct 96 ms 32700 KB Output is correct
9 Correct 173 ms 29004 KB Output is correct
10 Correct 128 ms 35908 KB Output is correct
11 Correct 155 ms 31816 KB Output is correct
12 Correct 168 ms 29684 KB Output is correct
13 Correct 133 ms 29920 KB Output is correct
14 Correct 135 ms 30032 KB Output is correct
15 Correct 131 ms 30092 KB Output is correct
16 Correct 115 ms 30124 KB Output is correct
17 Correct 35 ms 19540 KB Output is correct
18 Correct 55 ms 20564 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 35536 KB Output is correct
2 Correct 100 ms 39600 KB Output is correct
3 Correct 54 ms 19832 KB Output is correct
4 Correct 150 ms 31596 KB Output is correct
5 Correct 243 ms 31588 KB Output is correct
6 Correct 156 ms 30884 KB Output is correct
7 Correct 137 ms 30992 KB Output is correct
8 Correct 129 ms 30984 KB Output is correct
9 Correct 123 ms 31248 KB Output is correct
10 Correct 32 ms 19532 KB Output is correct
11 Incorrect 27 ms 19804 KB For each person outside the committee there should be someone in the committee who they dislike.
12 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 18268 KB Output is correct
2 Correct 6 ms 18276 KB Output is correct
3 Correct 6 ms 18012 KB Output is correct
4 Correct 9 ms 18012 KB Output is correct
5 Correct 7 ms 18008 KB Output is correct
6 Correct 7 ms 18012 KB Output is correct
7 Correct 7 ms 18012 KB Output is correct
8 Correct 7 ms 18108 KB Output is correct
9 Correct 6 ms 18012 KB Output is correct
10 Incorrect 5 ms 18012 KB For each person outside the committee there should be someone in the committee who they dislike.
11 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 35536 KB Output is correct
2 Correct 104 ms 35480 KB Output is correct
3 Correct 8 ms 18008 KB Output is correct
4 Correct 40 ms 25148 KB Output is correct
5 Correct 65 ms 29520 KB Output is correct
6 Correct 101 ms 39148 KB Output is correct
7 Correct 58 ms 19892 KB Output is correct
8 Correct 96 ms 32700 KB Output is correct
9 Correct 173 ms 29004 KB Output is correct
10 Correct 128 ms 35908 KB Output is correct
11 Correct 155 ms 31816 KB Output is correct
12 Correct 168 ms 29684 KB Output is correct
13 Correct 133 ms 29920 KB Output is correct
14 Correct 135 ms 30032 KB Output is correct
15 Correct 131 ms 30092 KB Output is correct
16 Correct 115 ms 30124 KB Output is correct
17 Correct 35 ms 19540 KB Output is correct
18 Correct 55 ms 20564 KB Output is correct
19 Correct 100 ms 35536 KB Output is correct
20 Correct 100 ms 39600 KB Output is correct
21 Correct 54 ms 19832 KB Output is correct
22 Correct 150 ms 31596 KB Output is correct
23 Correct 243 ms 31588 KB Output is correct
24 Correct 156 ms 30884 KB Output is correct
25 Correct 137 ms 30992 KB Output is correct
26 Correct 129 ms 30984 KB Output is correct
27 Correct 123 ms 31248 KB Output is correct
28 Correct 32 ms 19532 KB Output is correct
29 Incorrect 27 ms 19804 KB For each person outside the committee there should be someone in the committee who they dislike.
30 Halted 0 ms 0 KB -