10010 | 2024-03-24 08:26:55 | 111 | Kritikus munkák | cpp17 | Wrong answer 0/100 | 83ms | 42676 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N,M;
cin>>N>>M;
vector<vector<int>>g(N+1);
vector<int>c(N+1);
for(int i=0;i<M;i++){
int a,b;
cin>>a>>b;
g[a].push_back(b);
c[b]++;
}
for(int i=1;i<=N;i++){
if(c[i]==0){
g[0].push_back(i);
}
}
vector<int>a(N+1);
vector<int>p;
int s=0;
while(true){
p.push_back(s);
a[s]=p.size();
int z=0;
for(int i:g[s]){
if(!a[i]){
z=i;
break;
}
}
if(!z){
break;
}
s=z;
}
int h=0;
auto dfs=[&](auto self,int i)->void{
if(a[i]){
h=max(h,a[i]);
return;
}
a[i]=-1;
for(int j:g[i]){
self(self,j);
}
};
for(int i:p){
if(h>a[i]){
a[i]=-1;
}
for(int j:g[i]){
dfs(dfs,j);
}
}
vector<int>ans;
for(int i=1;i<=N;i++){
if(a[i]>0){
ans.push_back(i);
}
}
cout<<ans.size()<<'\n';
for(int i:ans){
cout<<i<<' ';
}
cout<<'\n';
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1828 KiB | ||||
2 | Accepted | 52ms | 14508 KiB | ||||
subtask2 | 0/25 | ||||||
3 | Wrong answer | 3ms | 3932 KiB | ||||
4 | Accepted | 3ms | 4308 KiB | ||||
5 | Accepted | 3ms | 4444 KiB | ||||
6 | Accepted | 3ms | 4388 KiB | ||||
7 | Wrong answer | 4ms | 4712 KiB | ||||
subtask3 | 0/25 | ||||||
8 | Wrong answer | 14ms | 6736 KiB | ||||
9 | Wrong answer | 8ms | 6432 KiB | ||||
10 | Wrong answer | 8ms | 6512 KiB | ||||
11 | Wrong answer | 12ms | 7476 KiB | ||||
12 | Wrong answer | 10ms | 7672 KiB | ||||
subtask4 | 0/25 | ||||||
13 | Wrong answer | 41ms | 15048 KiB | ||||
14 | Accepted | 39ms | 17476 KiB | ||||
15 | Accepted | 39ms | 18672 KiB | ||||
16 | Accepted | 39ms | 20284 KiB | ||||
17 | Accepted | 37ms | 21428 KiB | ||||
subtask5 | 0/25 | ||||||
18 | Accepted | 79ms | 32512 KiB | ||||
19 | Wrong answer | 79ms | 35176 KiB | ||||
20 | Wrong answer | 83ms | 38152 KiB | ||||
21 | Wrong answer | 79ms | 40548 KiB | ||||
22 | Wrong answer | 79ms | 42676 KiB |