1239 | 2022-03-28 16:17:12 | k_balint | Turista járatok | cpp14 | Runtime error 20/100 | 136ms | 53616 KiB |
#include <bits/stdc++.h>
using namespace std;
const int c=40004;
struct edge{
int v,id;
edge(int vv, int i){
v=vv; id=i;
}
edge(){
v=id=0;
}
};
int n,m,k;
vector<edge> adj[c];
int t[c],l[c];
bool used[10*c];
stack<int> s;
int tt; int cnt;
vector<int> comp[3*c];
int cut[c];
int ecmp[10*c];
bool good[3*c];
bool cut_cmp[3*c];
void new_comp(int id){
while(!s.empty() && s.top() != id){
int cur=s.top();
s.pop();
if(cur<=k) good[cnt]=1;
ecmp[cur]=cnt;
comp[cnt].push_back(cur);
}
if(!s.empty()){
int cur=s.top();
s.pop();
if(cur<=k) good[cnt]=1;
ecmp[cur]=cnt;
comp[cnt].push_back(cur);
}
++cnt;
}
vector<int> tree[3*c];
vector<edge> edges;
void dfs(int v, int p){
t[v]=l[v]=tt++;
bool children=0;
for(edge x:adj[v]){
if(x.id==p) continue;
if(!used[x.id]){
used[x.id]=1;
s.push(x.id);
}
if(!t[x.v]){
dfs(x.v,x.id);
l[v]=min(l[v],l[x.v]);
if(v==1?children:l[x.v]>=t[v]){
if(!cut[v]){
cut_cmp[cnt]=1;
cut[v]=cnt;
comp[cnt].push_back(v); ++cnt;
}
tree[cut[v]].push_back(cnt);
tree[cnt].push_back(cut[v]);
new_comp(x.id);
}
children=1;
}
else l[v]=min(l[v],t[x.v]);
}
if(cut[v] && p!=0){
edges.push_back(edge(cut[v],p));
}
if(v==1 && !s.empty()){
if(cut[v]){
tree[cut[v]].push_back(cnt);
tree[cnt].push_back(cut[v]);
}
new_comp(-1);
}
}
bool vis[3*c];
void dfs2(int v, bool g){
vis[v]=1; good[v]|=g;
for(int x:tree[v]){
if(!vis[x]){
dfs2(x,good[v]);
}
}
}
bool ans[c];
edge edg[4*c];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int a,b; cin>>a>>b;
edg[i]=edge(a,b);
adj[a].push_back(edge(b,i));
adj[b].push_back(edge(a,i));
}
tt=1; cnt=1;
dfs(1,0);
for(edge x:edges){
tree[x.v].push_back(ecmp[x.id]);
tree[ecmp[x.id]].push_back(x.v);
}
if(adj[1].empty()){
cout << 0 << endl;
return 0;
}
if(!cut[1]) dfs2(ecmp[adj[1][0].id],0);
else dfs2(cut[1],0);
for(int i=1;i<cnt;i++){
if(!good[i]) continue;
if(cut_cmp[i]){
ans[comp[i][0]]=1;
continue;
}
for(int x:comp[i]){
int a=edg[x].v;
int b=edg[x].id;
if(!cut[a]) ans[a]=1;
if(!cut[b]) ans[b]=1;
}
}
ans[1]=0;
int ans2=0;
for(int i=1;i<=n;i++){
if(ans[i]) ++ans2;
}
cout << ans2 << '\n';
for(int i=1;i<=n;i++){
if(ans[i]){
cout << i << ' ';
}
}
cout << endl;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 9ms | 17516 KiB | ||||
2 | Accepted | 17ms | 19512 KiB | ||||
subtask2 | 10/10 | ||||||
3 | Accepted | 8ms | 17668 KiB | ||||
4 | Accepted | 8ms | 17680 KiB | ||||
5 | Accepted | 8ms | 17684 KiB | ||||
6 | Accepted | 8ms | 17684 KiB | ||||
7 | Accepted | 10ms | 17696 KiB | ||||
subtask3 | 10/10 | ||||||
8 | Accepted | 9ms | 17692 KiB | ||||
9 | Accepted | 8ms | 17692 KiB | ||||
10 | Accepted | 8ms | 17708 KiB | ||||
11 | Accepted | 12ms | 18124 KiB | ||||
12 | Accepted | 13ms | 19424 KiB | ||||
subtask4 | 0/10 | ||||||
13 | Accepted | 16ms | 21164 KiB | ||||
14 | Accepted | 8ms | 17868 KiB | ||||
15 | Accepted | 8ms | 18092 KiB | ||||
16 | Accepted | 9ms | 18292 KiB | ||||
17 | Runtime error | 133ms | 42468 KiB | ||||
18 | Accepted | 52ms | 31116 KiB | ||||
19 | Accepted | 78ms | 35172 KiB | ||||
20 | Accepted | 59ms | 33548 KiB | ||||
subtask5 | 0/10 | ||||||
21 | Accepted | 14ms | 26992 KiB | ||||
22 | Accepted | 10ms | 25392 KiB | ||||
23 | Accepted | 8ms | 25416 KiB | ||||
24 | Accepted | 8ms | 25440 KiB | ||||
25 | Runtime error | 97ms | 43328 KiB | ||||
26 | Accepted | 17ms | 29936 KiB | ||||
27 | Accepted | 16ms | 30064 KiB | ||||
subtask6 | 0/60 | ||||||
28 | Accepted | 8ms | 28592 KiB | ||||
29 | Accepted | 9ms | 28624 KiB | ||||
30 | Accepted | 10ms | 28844 KiB | ||||
31 | Accepted | 12ms | 29084 KiB | ||||
32 | Accepted | 10ms | 29212 KiB | ||||
33 | Accepted | 12ms | 29504 KiB | ||||
34 | Accepted | 17ms | 30540 KiB | ||||
35 | Accepted | 17ms | 30680 KiB | ||||
36 | Accepted | 16ms | 30836 KiB | ||||
37 | Runtime error | 136ms | 53616 KiB | ||||
38 | Accepted | 54ms | 42156 KiB | ||||
39 | Accepted | 56ms | 43168 KiB | ||||
40 | Accepted | 54ms | 44076 KiB | ||||
41 | Accepted | 57ms | 44972 KiB | ||||
42 | Accepted | 54ms | 45824 KiB | ||||
43 | Accepted | 57ms | 46732 KiB | ||||
44 | Accepted | 52ms | 47652 KiB | ||||
45 | Accepted | 82ms | 51824 KiB | ||||
46 | Accepted | 57ms | 50060 KiB | ||||
47 | Accepted | 56ms | 50984 KiB | ||||
48 | Accepted | 61ms | 51632 KiB | ||||
49 | Accepted | 54ms | 52596 KiB | ||||
50 | Accepted | 54ms | 53460 KiB |