101422024-03-28 15:18:12111Turista járatokcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1836 KiB
2Elfogadva12ms7768 KiB
subtask20/10
3Elfogadva3ms2212 KiB
4Elfogadva3ms2436 KiB
5Hibás válasz3ms2512 KiB
6Hibás válasz3ms2576 KiB
7Hibás válasz3ms2604 KiB
subtask30/10
8Hibás válasz3ms2736 KiB
9Elfogadva3ms2900 KiB
10Elfogadva3ms3164 KiB
11Elfogadva3ms3472 KiB
12Elfogadva6ms5456 KiB
subtask40/10
13Elfogadva8ms8444 KiB
14Elfogadva3ms3324 KiB
15Elfogadva4ms3992 KiB
16Elfogadva4ms4724 KiB
17Hibás válasz146ms55388 KiB
18Hibás válasz54ms26148 KiB
19Hibás válasz65ms28092 KiB
20Hibás válasz50ms26400 KiB
subtask50/10
21Elfogadva10ms9420 KiB
22Elfogadva3ms4232 KiB
23Hibás válasz3ms4352 KiB
24Hibás válasz3ms4356 KiB
25Hibás válasz75ms22900 KiB
26Hibás válasz8ms7244 KiB
27Hibás válasz8ms7180 KiB
subtask60/60
28Hibás válasz3ms4648 KiB
29Elfogadva3ms4580 KiB
30Elfogadva4ms4984 KiB
31Hibás válasz4ms5444 KiB
32Hibás válasz6ms6244 KiB
33Elfogadva7ms7092 KiB
34Elfogadva10ms9908 KiB
35Elfogadva10ms10068 KiB
36Elfogadva10ms10028 KiB
37Hibás válasz137ms55908 KiB
38Hibás válasz50ms26968 KiB
39Hibás válasz50ms26968 KiB
40Hibás válasz50ms26928 KiB
41Hibás válasz50ms26932 KiB
42Hibás válasz50ms26924 KiB
43Hibás válasz50ms26984 KiB
44Hibás válasz50ms26968 KiB
45Hibás válasz65ms28876 KiB
46Hibás válasz50ms27072 KiB
47Hibás válasz50ms27032 KiB
48Hibás válasz52ms27220 KiB
49Hibás válasz50ms27072 KiB
50Hibás válasz50ms27036 KiB