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