10143 | 2024-03-28 15:18:52 | 111 | Turista járatok | cpp17 | Wrong answer 0/100 | 148ms | 56192 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,1);
}
};
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 | 1832 KiB | ||||
2 | Accepted | 10ms | 7624 KiB | ||||
subtask2 | 0/10 | ||||||
3 | Wrong answer | 3ms | 2248 KiB | ||||
4 | Wrong answer | 3ms | 2468 KiB | ||||
5 | Wrong answer | 3ms | 2700 KiB | ||||
6 | Wrong answer | 3ms | 2820 KiB | ||||
7 | Wrong answer | 3ms | 2932 KiB | ||||
subtask3 | 0/10 | ||||||
8 | Wrong answer | 3ms | 2984 KiB | ||||
9 | Accepted | 3ms | 3020 KiB | ||||
10 | Accepted | 3ms | 3132 KiB | ||||
11 | Accepted | 3ms | 3716 KiB | ||||
12 | Accepted | 6ms | 5692 KiB | ||||
subtask4 | 0/10 | ||||||
13 | Accepted | 9ms | 8680 KiB | ||||
14 | Accepted | 3ms | 3552 KiB | ||||
15 | Accepted | 3ms | 4192 KiB | ||||
16 | Accepted | 4ms | 4552 KiB | ||||
17 | Wrong answer | 148ms | 55368 KiB | ||||
18 | Wrong answer | 54ms | 26692 KiB | ||||
19 | Wrong answer | 70ms | 28632 KiB | ||||
20 | Wrong answer | 50ms | 26556 KiB | ||||
subtask5 | 0/10 | ||||||
21 | Accepted | 10ms | 9528 KiB | ||||
22 | Wrong answer | 3ms | 4428 KiB | ||||
23 | Wrong answer | 3ms | 4460 KiB | ||||
24 | Wrong answer | 3ms | 4608 KiB | ||||
25 | Wrong answer | 76ms | 22792 KiB | ||||
26 | Wrong answer | 8ms | 7068 KiB | ||||
27 | Wrong answer | 8ms | 7064 KiB | ||||
subtask6 | 0/60 | ||||||
28 | Wrong answer | 3ms | 4740 KiB | ||||
29 | Accepted | 3ms | 4728 KiB | ||||
30 | Accepted | 4ms | 5244 KiB | ||||
31 | Wrong answer | 4ms | 5800 KiB | ||||
32 | Wrong answer | 6ms | 6460 KiB | ||||
33 | Accepted | 7ms | 7252 KiB | ||||
34 | Accepted | 10ms | 10072 KiB | ||||
35 | Accepted | 10ms | 10192 KiB | ||||
36 | Accepted | 12ms | 10328 KiB | ||||
37 | Wrong answer | 136ms | 56192 KiB | ||||
38 | Wrong answer | 54ms | 27212 KiB | ||||
39 | Wrong answer | 54ms | 27460 KiB | ||||
40 | Wrong answer | 54ms | 27420 KiB | ||||
41 | Wrong answer | 56ms | 27596 KiB | ||||
42 | Wrong answer | 52ms | 27548 KiB | ||||
43 | Wrong answer | 56ms | 27552 KiB | ||||
44 | Wrong answer | 50ms | 27592 KiB | ||||
45 | Wrong answer | 70ms | 29500 KiB | ||||
46 | Wrong answer | 50ms | 27556 KiB | ||||
47 | Wrong answer | 54ms | 27552 KiB | ||||
48 | Wrong answer | 56ms | 27548 KiB | ||||
49 | Wrong answer | 54ms | 27552 KiB | ||||
50 | Wrong answer | 54ms | 27696 KiB |