Submission #1174056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174056		kininged	Pastiri (COI20_pastiri)	C++20	0 / 100	1099 ms	68804 KiB

pastiri

#include <bits/stdc++.h>
using namespace std;
const int N=5e5+100;
int n,k,w[N],dpt[N],fat[N],v[N];
bool vis[N];
vector<int>a[N],ba[N],res;
queue<int>q;
void dfs(int id,int fa)
{
	fat[id]=fa;
	dpt[id]=dpt[fa]+1;
	for(int i=0;i<a[id].size();i++)
	{
		int son=a[id][i];
		if(son==fa)continue;
		dfs(son,id);
	}
	return ;
}
void bfs()
{
	int t=1;
	while(q.size())
	{
		t++;
		int size=q.size();
		for(int i=1;i<=size;i++)
		{
			int id=q.front();
			q.pop();
			for(int j=0;j<a[id].size();j++)
			{
				int son=a[id][j];
				if(v[son])continue;
				v[son]=t;
				q.push(son);
			}
		}
	}
}
void solve(int id,int len)
{
	vis[id]=true;
	if(len==0)return ;
	for(int i=0;i<a[id].size();i++)
	{
		int son=a[id][i];
		solve(son,len-1);
	}
	return ; 
}
int main(){
	cin>>n>>k;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1,0);
	for(int i=1;i<=k;i++)
	{
		cin>>w[i];
		ba[dpt[w[i]]].push_back(w[i]);
		q.push(w[i]);
		v[w[i]]=1;
	}
	bfs();
	for(int i=5e5+1;i>=0;i--)
	{
		for(int j=0;j<ba[i].size();j++)
		{
			int son=ba[i][j];
			if(vis[son])continue;
			int now=son;
			while(fat[now]&&v[fat[now]]==v[now]+1) now=fat[now];
			res.push_back(now);
			solve(now,dpt[son]-dpt[now]);
		}
	}
	cout<<res.size()<<endl;
	for(int i=0;i<res.size();i++)
		cout<<res[i]<<" ";
	return 0;
}

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