101432024-03-28 15:18:52111Turista járatokcpp17Hibás válasz 0/100148ms56192 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Hibás válasz3ms1832 KiB
2Elfogadva10ms7624 KiB
subtask20/10
3Hibás válasz3ms2248 KiB
4Hibás válasz3ms2468 KiB
5Hibás válasz3ms2700 KiB
6Hibás válasz3ms2820 KiB
7Hibás válasz3ms2932 KiB
subtask30/10
8Hibás válasz3ms2984 KiB
9Elfogadva3ms3020 KiB
10Elfogadva3ms3132 KiB
11Elfogadva3ms3716 KiB
12Elfogadva6ms5692 KiB
subtask40/10
13Elfogadva9ms8680 KiB
14Elfogadva3ms3552 KiB
15Elfogadva3ms4192 KiB
16Elfogadva4ms4552 KiB
17Hibás válasz148ms55368 KiB
18Hibás válasz54ms26692 KiB
19Hibás válasz70ms28632 KiB
20Hibás válasz50ms26556 KiB
subtask50/10
21Elfogadva10ms9528 KiB
22Hibás válasz3ms4428 KiB
23Hibás válasz3ms4460 KiB
24Hibás válasz3ms4608 KiB
25Hibás válasz76ms22792 KiB
26Hibás válasz8ms7068 KiB
27Hibás válasz8ms7064 KiB
subtask60/60
28Hibás válasz3ms4740 KiB
29Elfogadva3ms4728 KiB
30Elfogadva4ms5244 KiB
31Hibás válasz4ms5800 KiB
32Hibás válasz6ms6460 KiB
33Elfogadva7ms7252 KiB
34Elfogadva10ms10072 KiB
35Elfogadva10ms10192 KiB
36Elfogadva12ms10328 KiB
37Hibás válasz136ms56192 KiB
38Hibás válasz54ms27212 KiB
39Hibás válasz54ms27460 KiB
40Hibás válasz54ms27420 KiB
41Hibás válasz56ms27596 KiB
42Hibás válasz52ms27548 KiB
43Hibás válasz56ms27552 KiB
44Hibás válasz50ms27592 KiB
45Hibás válasz70ms29500 KiB
46Hibás válasz50ms27556 KiB
47Hibás válasz54ms27552 KiB
48Hibás válasz56ms27548 KiB
49Hibás válasz54ms27552 KiB
50Hibás válasz54ms27696 KiB