10142 2024. 03. 28 15:18:12 111 Turista járatok cpp17 Hibás válasz 0/100 146ms 55908 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 Elfogadva 3ms 1836 KiB
2 Elfogadva 12ms 7768 KiB
subtask2 0/10
3 Elfogadva 3ms 2212 KiB
4 Elfogadva 3ms 2436 KiB
5 Hibás válasz 3ms 2512 KiB
6 Hibás válasz 3ms 2576 KiB
7 Hibás válasz 3ms 2604 KiB
subtask3 0/10
8 Hibás válasz 3ms 2736 KiB
9 Elfogadva 3ms 2900 KiB
10 Elfogadva 3ms 3164 KiB
11 Elfogadva 3ms 3472 KiB
12 Elfogadva 6ms 5456 KiB
subtask4 0/10
13 Elfogadva 8ms 8444 KiB
14 Elfogadva 3ms 3324 KiB
15 Elfogadva 4ms 3992 KiB
16 Elfogadva 4ms 4724 KiB
17 Hibás válasz 146ms 55388 KiB
18 Hibás válasz 54ms 26148 KiB
19 Hibás válasz 65ms 28092 KiB
20 Hibás válasz 50ms 26400 KiB
subtask5 0/10
21 Elfogadva 10ms 9420 KiB
22 Elfogadva 3ms 4232 KiB
23 Hibás válasz 3ms 4352 KiB
24 Hibás válasz 3ms 4356 KiB
25 Hibás válasz 75ms 22900 KiB
26 Hibás válasz 8ms 7244 KiB
27 Hibás válasz 8ms 7180 KiB
subtask6 0/60
28 Hibás válasz 3ms 4648 KiB
29 Elfogadva 3ms 4580 KiB
30 Elfogadva 4ms 4984 KiB
31 Hibás válasz 4ms 5444 KiB
32 Hibás válasz 6ms 6244 KiB
33 Elfogadva 7ms 7092 KiB
34 Elfogadva 10ms 9908 KiB
35 Elfogadva 10ms 10068 KiB
36 Elfogadva 10ms 10028 KiB
37 Hibás válasz 137ms 55908 KiB
38 Hibás válasz 50ms 26968 KiB
39 Hibás válasz 50ms 26968 KiB
40 Hibás válasz 50ms 26928 KiB
41 Hibás válasz 50ms 26932 KiB
42 Hibás válasz 50ms 26924 KiB
43 Hibás válasz 50ms 26984 KiB
44 Hibás válasz 50ms 26968 KiB
45 Hibás válasz 65ms 28876 KiB
46 Hibás válasz 50ms 27072 KiB
47 Hibás válasz 50ms 27032 KiB
48 Hibás válasz 52ms 27220 KiB
49 Hibás válasz 50ms 27072 KiB
50 Hibás válasz 50ms 27036 KiB