Submission #334294

#	Time	Username	Problem	Language	Result	Execution time	Memory
334294		limabeans	Pastiri (COI20_pastiri)	C++17	100 / 100	795 ms	90292 KiB

pastiri

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;




int n,k;
vector<int> g[maxn];
vector<int> a;

int par[maxn];
int dep[maxn];

void dfs(int at, int p) {
    for (int to: g[at]) {
	if (to == p) continue;
	par[to]=at;
	dep[to]=1+dep[at];
	dfs(to,at);
    }
}

int rad[maxn];

void gen_rad() {
    for (int i=1; i<=n; i++) {
	rad[i]=-1;
    }
    queue<int> qq;
    for (int x: a) {
	rad[x]=0;
	qq.push(x);
    }
    while (qq.size()) {
	int at = qq.front();
	qq.pop();
	for (int to: g[at]) {
	    if (rad[to]==-1) {
		rad[to]=1+rad[at];
		qq.push(to);
	    }
	}
    }
}


bool done[maxn];

void mark_done(int x) {
    queue<int> qq;
    qq.push(x);
    while (qq.size()) {
	int at = qq.front();
	qq.pop();
	done[at] = true;
	for (int to: g[at]) {
	    if (done[to]) continue;
	    if (rad[to] == rad[at]-1) {
		qq.push(to);
	    }
	}
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>k;
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	g[u].push_back(v);
	g[v].push_back(u);
    }

    a.resize(k);
    for (int i=0; i<k; i++) {
	cin>>a[i];
    }

    dfs(1,0);
    gen_rad();

    sort(a.begin(), a.end(), [&](int x, int y) {
	    return dep[x]<dep[y];
	});
    reverse(a.begin(),a.end());


    vector<int> ans;

    for (int x: a) {
	if (done[x]) continue;
	int at = x;
	while (rad[par[at]] == 1+rad[at]) {
	    at = par[at];
	}
	ans.push_back(at);
	mark_done(at);
    }


    cout<<ans.size()<<"\n";
    sort(ans.begin(),ans.end());
    for (int x: ans) cout<<x<<" ";
    cout<<endl;
    
    
    return 0;
}

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