| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 959990 | 2024-04-09T11:56:45 Z | pcc | Povjerenstvo (COI22_povjerenstvo) | C++17 | 219 ms | 39628 KB |
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long
const int mxn = 5e5+10;
int N,M;
vector<int> paths[mxn];
int deg[mxn];
queue<int> q;
int ans[mxn];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>M;
memset(ans,-1,sizeof(ans));
for(int i = 1;i<=M;i++){
int a,b;
cin>>a>>b;
deg[a]++;
paths[b].push_back(a);
}
for(int i = 1;i<=N;i++)if(!deg[i])q.push(i);
while(!q.empty()){
auto now = q.front();
q.pop();
if(ans[now] == -1)ans[now] = 1;
for(auto nxt:paths[now]){
deg[nxt]--;
if(!deg[nxt])q.push(nxt);
if(ans[now] == 1){
if(ans[nxt] == -1)ans[nxt] = 0;
}
}
}
vector<int> v;
for(int i = 1;i<=N;i++){
if(ans[i] == 1)v.push_back(i);
}
cout<<v.size()<<'\n';
for(auto &i:v)cout<<i<<' ';cout<<'\n';
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 110 ms | 33616 KB | Output is correct |
| 2 | Correct | 96 ms | 33476 KB | Output is correct |
| 3 | Correct | 4 ms | 15960 KB | Output is correct |
| 4 | Correct | 35 ms | 23128 KB | Output is correct |
| 5 | Correct | 60 ms | 27492 KB | Output is correct |
| 6 | Correct | 94 ms | 37160 KB | Output is correct |
| 7 | Correct | 56 ms | 24172 KB | Output is correct |
| 8 | Correct | 92 ms | 34240 KB | Output is correct |
| 9 | Correct | 181 ms | 33560 KB | Output is correct |
| 10 | Correct | 117 ms | 39628 KB | Output is correct |
| 11 | Correct | 160 ms | 36120 KB | Output is correct |
| 12 | Correct | 176 ms | 33868 KB | Output is correct |
| 13 | Correct | 144 ms | 34736 KB | Output is correct |
| 14 | Correct | 131 ms | 34348 KB | Output is correct |
| 15 | Correct | 128 ms | 34456 KB | Output is correct |
| 16 | Correct | 123 ms | 34408 KB | Output is correct |
| 17 | Correct | 32 ms | 19796 KB | Output is correct |
| 18 | Correct | 56 ms | 22356 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 93 ms | 33740 KB | Output is correct |
| 2 | Correct | 95 ms | 37764 KB | Output is correct |
| 3 | Correct | 56 ms | 23748 KB | Output is correct |
| 4 | Correct | 151 ms | 35656 KB | Output is correct |
| 5 | Incorrect | 219 ms | 36164 KB | For each person outside the committee there should be someone in the committee who they dislike. |
| 6 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 ms | 16220 KB | Output is correct |
| 2 | Correct | 5 ms | 16136 KB | Output is correct |
| 3 | Correct | 6 ms | 15964 KB | Output is correct |
| 4 | Correct | 5 ms | 16220 KB | Output is correct |
| 5 | Incorrect | 5 ms | 16220 KB | For each person outside the committee there should be someone in the committee who they dislike. |
| 6 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 110 ms | 33616 KB | Output is correct |
| 2 | Correct | 96 ms | 33476 KB | Output is correct |
| 3 | Correct | 4 ms | 15960 KB | Output is correct |
| 4 | Correct | 35 ms | 23128 KB | Output is correct |
| 5 | Correct | 60 ms | 27492 KB | Output is correct |
| 6 | Correct | 94 ms | 37160 KB | Output is correct |
| 7 | Correct | 56 ms | 24172 KB | Output is correct |
| 8 | Correct | 92 ms | 34240 KB | Output is correct |
| 9 | Correct | 181 ms | 33560 KB | Output is correct |
| 10 | Correct | 117 ms | 39628 KB | Output is correct |
| 11 | Correct | 160 ms | 36120 KB | Output is correct |
| 12 | Correct | 176 ms | 33868 KB | Output is correct |
| 13 | Correct | 144 ms | 34736 KB | Output is correct |
| 14 | Correct | 131 ms | 34348 KB | Output is correct |
| 15 | Correct | 128 ms | 34456 KB | Output is correct |
| 16 | Correct | 123 ms | 34408 KB | Output is correct |
| 17 | Correct | 32 ms | 19796 KB | Output is correct |
| 18 | Correct | 56 ms | 22356 KB | Output is correct |
| 19 | Correct | 93 ms | 33740 KB | Output is correct |
| 20 | Correct | 95 ms | 37764 KB | Output is correct |
| 21 | Correct | 56 ms | 23748 KB | Output is correct |
| 22 | Correct | 151 ms | 35656 KB | Output is correct |
| 23 | Incorrect | 219 ms | 36164 KB | For each person outside the committee there should be someone in the committee who they dislike. |
| 24 | Halted | 0 ms | 0 KB | - |