10142 | 2024-03-28 15:18:12 | 111 | Turista járatok | cpp17 | Wrong answer 0/100 | 146ms | 55908 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 | Accepted | 3ms | 1836 KiB | ||||
2 | Accepted | 12ms | 7768 KiB | ||||
subtask2 | 0/10 | ||||||
3 | Accepted | 3ms | 2212 KiB | ||||
4 | Accepted | 3ms | 2436 KiB | ||||
5 | Wrong answer | 3ms | 2512 KiB | ||||
6 | Wrong answer | 3ms | 2576 KiB | ||||
7 | Wrong answer | 3ms | 2604 KiB | ||||
subtask3 | 0/10 | ||||||
8 | Wrong answer | 3ms | 2736 KiB | ||||
9 | Accepted | 3ms | 2900 KiB | ||||
10 | Accepted | 3ms | 3164 KiB | ||||
11 | Accepted | 3ms | 3472 KiB | ||||
12 | Accepted | 6ms | 5456 KiB | ||||
subtask4 | 0/10 | ||||||
13 | Accepted | 8ms | 8444 KiB | ||||
14 | Accepted | 3ms | 3324 KiB | ||||
15 | Accepted | 4ms | 3992 KiB | ||||
16 | Accepted | 4ms | 4724 KiB | ||||
17 | Wrong answer | 146ms | 55388 KiB | ||||
18 | Wrong answer | 54ms | 26148 KiB | ||||
19 | Wrong answer | 65ms | 28092 KiB | ||||
20 | Wrong answer | 50ms | 26400 KiB | ||||
subtask5 | 0/10 | ||||||
21 | Accepted | 10ms | 9420 KiB | ||||
22 | Accepted | 3ms | 4232 KiB | ||||
23 | Wrong answer | 3ms | 4352 KiB | ||||
24 | Wrong answer | 3ms | 4356 KiB | ||||
25 | Wrong answer | 75ms | 22900 KiB | ||||
26 | Wrong answer | 8ms | 7244 KiB | ||||
27 | Wrong answer | 8ms | 7180 KiB | ||||
subtask6 | 0/60 | ||||||
28 | Wrong answer | 3ms | 4648 KiB | ||||
29 | Accepted | 3ms | 4580 KiB | ||||
30 | Accepted | 4ms | 4984 KiB | ||||
31 | Wrong answer | 4ms | 5444 KiB | ||||
32 | Wrong answer | 6ms | 6244 KiB | ||||
33 | Accepted | 7ms | 7092 KiB | ||||
34 | Accepted | 10ms | 9908 KiB | ||||
35 | Accepted | 10ms | 10068 KiB | ||||
36 | Accepted | 10ms | 10028 KiB | ||||
37 | Wrong answer | 137ms | 55908 KiB | ||||
38 | Wrong answer | 50ms | 26968 KiB | ||||
39 | Wrong answer | 50ms | 26968 KiB | ||||
40 | Wrong answer | 50ms | 26928 KiB | ||||
41 | Wrong answer | 50ms | 26932 KiB | ||||
42 | Wrong answer | 50ms | 26924 KiB | ||||
43 | Wrong answer | 50ms | 26984 KiB | ||||
44 | Wrong answer | 50ms | 26968 KiB | ||||
45 | Wrong answer | 65ms | 28876 KiB | ||||
46 | Wrong answer | 50ms | 27072 KiB | ||||
47 | Wrong answer | 50ms | 27032 KiB | ||||
48 | Wrong answer | 52ms | 27220 KiB | ||||
49 | Wrong answer | 50ms | 27072 KiB | ||||
50 | Wrong answer | 50ms | 27036 KiB |