10144 2024. 03. 28 15:40:10 111 Turista járatok cpp17 Hibás válasz 0/100 150ms 56348 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Hibás válasz 3ms 1828 KiB
2 Elfogadva 12ms 7784 KiB
subtask2 0/10
3 Hibás válasz 3ms 2276 KiB
4 Hibás válasz 3ms 2620 KiB
5 Hibás válasz 3ms 2668 KiB
6 Hibás válasz 3ms 2884 KiB
7 Hibás válasz 3ms 3180 KiB
subtask3 0/10
8 Hibás válasz 3ms 3384 KiB
9 Elfogadva 3ms 3444 KiB
10 Elfogadva 3ms 3548 KiB
11 Elfogadva 3ms 4136 KiB
12 Elfogadva 6ms 6240 KiB
subtask4 0/10
13 Elfogadva 8ms 9052 KiB
14 Elfogadva 3ms 3976 KiB
15 Elfogadva 3ms 4364 KiB
16 Elfogadva 4ms 5032 KiB
17 Hibás válasz 150ms 55680 KiB
18 Hibás válasz 54ms 26880 KiB
19 Hibás válasz 70ms 28936 KiB
20 Hibás válasz 50ms 26856 KiB
subtask5 0/10
21 Elfogadva 10ms 9848 KiB
22 Hibás válasz 3ms 4772 KiB
23 Hibás válasz 3ms 5032 KiB
24 Hibás válasz 3ms 4884 KiB
25 Hibás válasz 79ms 23168 KiB
26 Hibás válasz 8ms 7700 KiB
27 Hibás válasz 8ms 7656 KiB
subtask6 0/60
28 Hibás válasz 3ms 5368 KiB
29 Elfogadva 3ms 5384 KiB
30 Elfogadva 4ms 5788 KiB
31 Hibás válasz 4ms 6308 KiB
32 Hibás válasz 6ms 6840 KiB
33 Elfogadva 7ms 7748 KiB
34 Elfogadva 10ms 10644 KiB
35 Elfogadva 10ms 10548 KiB
36 Elfogadva 10ms 10464 KiB
37 Hibás válasz 149ms 56348 KiB
38 Hibás válasz 50ms 27364 KiB
39 Hibás válasz 50ms 27364 KiB
40 Hibás válasz 54ms 27360 KiB
41 Hibás válasz 54ms 27360 KiB
42 Hibás válasz 54ms 27360 KiB
43 Hibás válasz 52ms 27512 KiB
44 Hibás válasz 54ms 27364 KiB
45 Hibás válasz 65ms 29524 KiB
46 Hibás válasz 54ms 27440 KiB
47 Hibás válasz 54ms 27360 KiB
48 Hibás válasz 52ms 27416 KiB
49 Hibás válasz 54ms 27360 KiB
50 Hibás válasz 52ms 27412 KiB