10144 | 2024-03-28 15:40:10 | 111 | Turista járatok | cpp17 | Wrong answer 0/100 | 150ms | 56348 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,K;
cin>>N>>M>>K;
vector<vector<int>>g(N+1),t(N+1);
vector<pair<int,int>>e;
for(int i=0;i<M;i++){
int a,b;
cin>>a>>b;
if(i<K){
t[a].push_back(b);
t[b].push_back(a);
e.emplace_back(a,b);
e.emplace_back(b,a);
}
else{
g[a].push_back(b);
g[b].push_back(a);
}
}
vector<int>v(N+1),w(N+1),p(N+1),ti(N+1),to(N+1);
vector<array<int,16>>up(N+1);
int ta=1;
auto dfs=[&](auto self,int i)->void{
w[i]=i;
ti[i]=ta++;
for(int j:g[i]){
if(v[j]){
if(v[j]<v[w[i]]){
w[i]=j;
}
continue;
}
v[j]=v[i]+1;
p[j]=i;
self(self,j);
if(v[w[j]]<v[w[i]]){
w[i]=w[j];
}
}
to[i]=ta++;
up[i][0]=p[i];
for(int j=1;j<16;j++){
up[i][j]=up[up[i][j-1]][j-1];
}
};
v[1]=1;
dfs(dfs,1);
ti[0]=0;
to[0]=ta;
auto des=[&](int a,int b)->bool{
return ti[a]<=ti[b]&&to[a]>=to[b];
};
auto lca=[&](int a,int b)->int{
while(!des(a,b)){
for(int i=1;;i++){
if(des(up[a][i],b)){
a=up[a][i-1];
break;
}
}
}
return a;
};
auto lcb=[&](int a,int b)->int{
if(des(a,b)){
return -1;
}
while(!des(p[a],b)){
for(int i=1;;i++){
if(des(p[up[a][i]],b)){
a=up[a][i-1];
break;
}
}
}
return a;
};
vector<int>u(N+1);
for(auto[a,b]:e){
if(!v[a]){
continue;
}
if(v[a]&&!v[b]){
u[b]=1;
continue;
}
// int x=lcb(a,b),y=lcb(b,a);
// if(x!=-1){
// u[x]=1;
// }
// if(y!=-1){
// u[y]=1;
// }
}
auto dfs2=[&](auto self,int i,int b)->void{
u[i]|=b;
b|=u[i];
for(int j:g[i]){
if(v[j]&&p[j]!=i){
continue;
}
v[j]=v[i]+1;
p[j]=i;
self(self,j,b);
}
for(int j:t[i]){
if(v[j]&&p[j]!=i){
continue;
}
v[j]=v[i]+1;
p[j]=i;
self(self,j,b);
}
};
dfs2(dfs2,1,0);
cout<<count(u.begin(),u.end(),1)<<'\n';
for(int i=1;i<=N;i++){
if(u[i]){
cout<<i<<' ';
}
}
cout<<'\n';
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Wrong answer | 3ms | 1828 KiB | ||||
2 | Accepted | 12ms | 7784 KiB | ||||
subtask2 | 0/10 | ||||||
3 | Wrong answer | 3ms | 2276 KiB | ||||
4 | Wrong answer | 3ms | 2620 KiB | ||||
5 | Wrong answer | 3ms | 2668 KiB | ||||
6 | Wrong answer | 3ms | 2884 KiB | ||||
7 | Wrong answer | 3ms | 3180 KiB | ||||
subtask3 | 0/10 | ||||||
8 | Wrong answer | 3ms | 3384 KiB | ||||
9 | Accepted | 3ms | 3444 KiB | ||||
10 | Accepted | 3ms | 3548 KiB | ||||
11 | Accepted | 3ms | 4136 KiB | ||||
12 | Accepted | 6ms | 6240 KiB | ||||
subtask4 | 0/10 | ||||||
13 | Accepted | 8ms | 9052 KiB | ||||
14 | Accepted | 3ms | 3976 KiB | ||||
15 | Accepted | 3ms | 4364 KiB | ||||
16 | Accepted | 4ms | 5032 KiB | ||||
17 | Wrong answer | 150ms | 55680 KiB | ||||
18 | Wrong answer | 54ms | 26880 KiB | ||||
19 | Wrong answer | 70ms | 28936 KiB | ||||
20 | Wrong answer | 50ms | 26856 KiB | ||||
subtask5 | 0/10 | ||||||
21 | Accepted | 10ms | 9848 KiB | ||||
22 | Wrong answer | 3ms | 4772 KiB | ||||
23 | Wrong answer | 3ms | 5032 KiB | ||||
24 | Wrong answer | 3ms | 4884 KiB | ||||
25 | Wrong answer | 79ms | 23168 KiB | ||||
26 | Wrong answer | 8ms | 7700 KiB | ||||
27 | Wrong answer | 8ms | 7656 KiB | ||||
subtask6 | 0/60 | ||||||
28 | Wrong answer | 3ms | 5368 KiB | ||||
29 | Accepted | 3ms | 5384 KiB | ||||
30 | Accepted | 4ms | 5788 KiB | ||||
31 | Wrong answer | 4ms | 6308 KiB | ||||
32 | Wrong answer | 6ms | 6840 KiB | ||||
33 | Accepted | 7ms | 7748 KiB | ||||
34 | Accepted | 10ms | 10644 KiB | ||||
35 | Accepted | 10ms | 10548 KiB | ||||
36 | Accepted | 10ms | 10464 KiB | ||||
37 | Wrong answer | 149ms | 56348 KiB | ||||
38 | Wrong answer | 50ms | 27364 KiB | ||||
39 | Wrong answer | 50ms | 27364 KiB | ||||
40 | Wrong answer | 54ms | 27360 KiB | ||||
41 | Wrong answer | 54ms | 27360 KiB | ||||
42 | Wrong answer | 54ms | 27360 KiB | ||||
43 | Wrong answer | 52ms | 27512 KiB | ||||
44 | Wrong answer | 54ms | 27364 KiB | ||||
45 | Wrong answer | 65ms | 29524 KiB | ||||
46 | Wrong answer | 54ms | 27440 KiB | ||||
47 | Wrong answer | 54ms | 27360 KiB | ||||
48 | Wrong answer | 52ms | 27416 KiB | ||||
49 | Wrong answer | 54ms | 27360 KiB | ||||
50 | Wrong answer | 52ms | 27412 KiB |