101432024-03-28 15:18:52111Turista járatokcpp17Wrong answer 0/100148ms56192 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer3ms1832 KiB
2Accepted10ms7624 KiB
subtask20/10
3Wrong answer3ms2248 KiB
4Wrong answer3ms2468 KiB
5Wrong answer3ms2700 KiB
6Wrong answer3ms2820 KiB
7Wrong answer3ms2932 KiB
subtask30/10
8Wrong answer3ms2984 KiB
9Accepted3ms3020 KiB
10Accepted3ms3132 KiB
11Accepted3ms3716 KiB
12Accepted6ms5692 KiB
subtask40/10
13Accepted9ms8680 KiB
14Accepted3ms3552 KiB
15Accepted3ms4192 KiB
16Accepted4ms4552 KiB
17Wrong answer148ms55368 KiB
18Wrong answer54ms26692 KiB
19Wrong answer70ms28632 KiB
20Wrong answer50ms26556 KiB
subtask50/10
21Accepted10ms9528 KiB
22Wrong answer3ms4428 KiB
23Wrong answer3ms4460 KiB
24Wrong answer3ms4608 KiB
25Wrong answer76ms22792 KiB
26Wrong answer8ms7068 KiB
27Wrong answer8ms7064 KiB
subtask60/60
28Wrong answer3ms4740 KiB
29Accepted3ms4728 KiB
30Accepted4ms5244 KiB
31Wrong answer4ms5800 KiB
32Wrong answer6ms6460 KiB
33Accepted7ms7252 KiB
34Accepted10ms10072 KiB
35Accepted10ms10192 KiB
36Accepted12ms10328 KiB
37Wrong answer136ms56192 KiB
38Wrong answer54ms27212 KiB
39Wrong answer54ms27460 KiB
40Wrong answer54ms27420 KiB
41Wrong answer56ms27596 KiB
42Wrong answer52ms27548 KiB
43Wrong answer56ms27552 KiB
44Wrong answer50ms27592 KiB
45Wrong answer70ms29500 KiB
46Wrong answer50ms27556 KiB
47Wrong answer54ms27552 KiB
48Wrong answer56ms27548 KiB
49Wrong answer54ms27552 KiB
50Wrong answer54ms27696 KiB