101442024-03-28 15:40:10111Turista járatokcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz3ms1828 KiB
2Elfogadva12ms7784 KiB
subtask20/10
3Hibás válasz3ms2276 KiB
4Hibás válasz3ms2620 KiB
5Hibás válasz3ms2668 KiB
6Hibás válasz3ms2884 KiB
7Hibás válasz3ms3180 KiB
subtask30/10
8Hibás válasz3ms3384 KiB
9Elfogadva3ms3444 KiB
10Elfogadva3ms3548 KiB
11Elfogadva3ms4136 KiB
12Elfogadva6ms6240 KiB
subtask40/10
13Elfogadva8ms9052 KiB
14Elfogadva3ms3976 KiB
15Elfogadva3ms4364 KiB
16Elfogadva4ms5032 KiB
17Hibás válasz150ms55680 KiB
18Hibás válasz54ms26880 KiB
19Hibás válasz70ms28936 KiB
20Hibás válasz50ms26856 KiB
subtask50/10
21Elfogadva10ms9848 KiB
22Hibás válasz3ms4772 KiB
23Hibás válasz3ms5032 KiB
24Hibás válasz3ms4884 KiB
25Hibás válasz79ms23168 KiB
26Hibás válasz8ms7700 KiB
27Hibás válasz8ms7656 KiB
subtask60/60
28Hibás válasz3ms5368 KiB
29Elfogadva3ms5384 KiB
30Elfogadva4ms5788 KiB
31Hibás válasz4ms6308 KiB
32Hibás válasz6ms6840 KiB
33Elfogadva7ms7748 KiB
34Elfogadva10ms10644 KiB
35Elfogadva10ms10548 KiB
36Elfogadva10ms10464 KiB
37Hibás válasz149ms56348 KiB
38Hibás válasz50ms27364 KiB
39Hibás válasz50ms27364 KiB
40Hibás válasz54ms27360 KiB
41Hibás válasz54ms27360 KiB
42Hibás válasz54ms27360 KiB
43Hibás válasz52ms27512 KiB
44Hibás válasz54ms27364 KiB
45Hibás válasz65ms29524 KiB
46Hibás válasz54ms27440 KiB
47Hibás válasz54ms27360 KiB
48Hibás válasz52ms27416 KiB
49Hibás válasz54ms27360 KiB
50Hibás válasz52ms27412 KiB