101442024-03-28 15:40:10111Turista járatokcpp17Wrong answer 0/100150ms56348 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Wrong answer3ms1828 KiB
2Accepted12ms7784 KiB
subtask20/10
3Wrong answer3ms2276 KiB
4Wrong answer3ms2620 KiB
5Wrong answer3ms2668 KiB
6Wrong answer3ms2884 KiB
7Wrong answer3ms3180 KiB
subtask30/10
8Wrong answer3ms3384 KiB
9Accepted3ms3444 KiB
10Accepted3ms3548 KiB
11Accepted3ms4136 KiB
12Accepted6ms6240 KiB
subtask40/10
13Accepted8ms9052 KiB
14Accepted3ms3976 KiB
15Accepted3ms4364 KiB
16Accepted4ms5032 KiB
17Wrong answer150ms55680 KiB
18Wrong answer54ms26880 KiB
19Wrong answer70ms28936 KiB
20Wrong answer50ms26856 KiB
subtask50/10
21Accepted10ms9848 KiB
22Wrong answer3ms4772 KiB
23Wrong answer3ms5032 KiB
24Wrong answer3ms4884 KiB
25Wrong answer79ms23168 KiB
26Wrong answer8ms7700 KiB
27Wrong answer8ms7656 KiB
subtask60/60
28Wrong answer3ms5368 KiB
29Accepted3ms5384 KiB
30Accepted4ms5788 KiB
31Wrong answer4ms6308 KiB
32Wrong answer6ms6840 KiB
33Accepted7ms7748 KiB
34Accepted10ms10644 KiB
35Accepted10ms10548 KiB
36Accepted10ms10464 KiB
37Wrong answer149ms56348 KiB
38Wrong answer50ms27364 KiB
39Wrong answer50ms27364 KiB
40Wrong answer54ms27360 KiB
41Wrong answer54ms27360 KiB
42Wrong answer54ms27360 KiB
43Wrong answer52ms27512 KiB
44Wrong answer54ms27364 KiB
45Wrong answer65ms29524 KiB
46Wrong answer54ms27440 KiB
47Wrong answer54ms27360 KiB
48Wrong answer52ms27416 KiB
49Wrong answer54ms27360 KiB
50Wrong answer52ms27412 KiB