Submission #1174058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174058		kininged	Pastiri (COI20_pastiri)	C++20	100 / 100	531 ms	71268 KiB

pastiri

//AC自动机
#include <bits/stdc++.h>
#define ll long long
#define N 500010
using namespace std;
vector<int> e[N]; 
int o[N],d[N],g[N],f[N];
bool vis[N];
int n,k;
void DeepSeek(int u,int fa)
{
	d[u]=d[fa]+1,f[u]=fa;
	for(auto v:e[u]) 
		if(v==fa) continue;
		else DeepSeek(v,u);
}
void bfs()
{
	queue<int> q;
	for(int i=1;i<=n;i++) g[i]=-1;
	for(int i=1;i<=k;i++) q.push(o[i]),g[o[i]]=0;
	while(q.size())
	{
		int u=q.front();q.pop();
		for(auto v:e[u])
			if(g[v]<0) g[v]=g[u]+1,q.push(v);
	}
}
void dfs(int u,int G)
{
	vis[u]=1;
	for(auto v:e[u])
		if(!vis[v]&&g[v]==G-1) dfs(v,G-1);
}
bool cmp(int a,int b)
{
	return d[a]>d[b];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>n>>k;
	int u,v;
	for(int i=1;i<n;i++)
	{
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	for(int i=1;i<=k;i++) cin>>o[i];
	DeepSeek(1,0);bfs();sort(o+1,o+1+k,cmp);
	set<int> ans;
	vis[0]=1;
	for(int i=1;i<=k;i++)
	{
		if(vis[o[i]]) continue;
		int now=o[i];
		while(g[f[now]]==g[now]+1) now=f[now];
		dfs(now,g[now]-g[o[i]]);ans.insert(now);
	}
	cout<<ans.size()<<"\n";
	for(auto v:ans) cout<<v<<" ";
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51