Submission #759593

#	Time	Username	Problem	Language	Result	Execution time	Memory
759593		NintsiChkhaidze	Pastiri (COI20_pastiri)	C++17	18 / 100	495 ms	82424 KiB

pastiri

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define pii pair <int,int>
#define left (h<<1),l,((l + r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;

const int N = 5e5 + 5,inf = 1e9;

int dis[N],d[N],m[N];
bool fix[N],vis[N];
vector <int> v[N],ans;

void dfs(int x,int par){

	d[x] = m[x] = -inf;
	if (fix[x]) d[x] = 0;
	
	for (int to: v[x]){
		if (to == par) continue;
		dfs(to,x);
		
		if (d[to] + 1 > dis[x]){
			//to-shi uechveli unda dasva cxvari
			ans.pb(to);
			d[to] = -inf;
			m[to] = max(dis[to],m[to]);
		}

		m[x] = max(m[x],m[to] - 1);
		d[x] = max(d[x],d[to] + 1);
	}

	if (m[x] >= d[x]) d[x] = -inf;
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,m;
	cin>>n>>m;

	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}
	
	for (int i = 1; i <= n; i++) 	
		dis[i] = inf;

	queue <int> q;
	for (int i = 1; i <= m; i++){
		int x;
		cin>>x;
		fix[x] = 1;
		dis[x] = 0;
		q.push(x);
	}

	while (q.size()){
		int x = q.front(); q.pop();
		vis[x] = 1;
		for (int to: v[x]){
			if (!vis[to]){
				vis[to] = 1;
				dis[to] = dis[x] + 1;
				q.push(to);
			}
		}
	}

	dfs(1,1);

	if (d[1] != -inf) ans.pb(1);
	cout<<ans.size()<<"\n";
	for (int x: ans) cout<<x<<" ";
}

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