101422024-03-28 15:18:12111Turista járatokcpp17Wrong answer 0/100146ms55908 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
1Accepted3ms1836 KiB
2Accepted12ms7768 KiB
subtask20/10
3Accepted3ms2212 KiB
4Accepted3ms2436 KiB
5Wrong answer3ms2512 KiB
6Wrong answer3ms2576 KiB
7Wrong answer3ms2604 KiB
subtask30/10
8Wrong answer3ms2736 KiB
9Accepted3ms2900 KiB
10Accepted3ms3164 KiB
11Accepted3ms3472 KiB
12Accepted6ms5456 KiB
subtask40/10
13Accepted8ms8444 KiB
14Accepted3ms3324 KiB
15Accepted4ms3992 KiB
16Accepted4ms4724 KiB
17Wrong answer146ms55388 KiB
18Wrong answer54ms26148 KiB
19Wrong answer65ms28092 KiB
20Wrong answer50ms26400 KiB
subtask50/10
21Accepted10ms9420 KiB
22Accepted3ms4232 KiB
23Wrong answer3ms4352 KiB
24Wrong answer3ms4356 KiB
25Wrong answer75ms22900 KiB
26Wrong answer8ms7244 KiB
27Wrong answer8ms7180 KiB
subtask60/60
28Wrong answer3ms4648 KiB
29Accepted3ms4580 KiB
30Accepted4ms4984 KiB
31Wrong answer4ms5444 KiB
32Wrong answer6ms6244 KiB
33Accepted7ms7092 KiB
34Accepted10ms9908 KiB
35Accepted10ms10068 KiB
36Accepted10ms10028 KiB
37Wrong answer137ms55908 KiB
38Wrong answer50ms26968 KiB
39Wrong answer50ms26968 KiB
40Wrong answer50ms26928 KiB
41Wrong answer50ms26932 KiB
42Wrong answer50ms26924 KiB
43Wrong answer50ms26984 KiB
44Wrong answer50ms26968 KiB
45Wrong answer65ms28876 KiB
46Wrong answer50ms27072 KiB
47Wrong answer50ms27032 KiB
48Wrong answer52ms27220 KiB
49Wrong answer50ms27072 KiB
50Wrong answer50ms27036 KiB