Submission #583194

# Submission time Handle Problem Language Result Execution time Memory
583194 2022-06-25T03:37:33 Z czhang2718 Pastiri (COI20_pastiri) C++17
100 / 100
627 ms 83508 KB
#include "bits/stdc++.h"
using namespace std;

typedef pair<int, int> pii;
#define f first
#define s second

const int N=5e5+1;
int n, k;
vector<int> adj[N];
bool mark[N];
int dp[N], d[N];
vector<int> ans;

void dfs(int x, int par){
	dp[x]=-1;
	if(!d[x]) mark[x]=1;
	for(int k:adj[x]){
		if(k==par) continue;
		dfs(k, x);
		if(mark[k]) mark[x]=1;
		dp[x]=max(dp[x], dp[k]-1);
	}
	if(mark[x] && dp[x]==d[x]) mark[x]=0;
	if(mark[x] && d[par]!=d[x]+1){
		ans.push_back(x);
		dp[x]=d[x];
		mark[x]=0;
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);

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

	for(int i=1; i<=n; i++){
		d[i]=-1;
	}

	queue<int> q;
	while(k--){
		int sheep;
		cin >> sheep;
		d[sheep]=0;
		q.push(sheep);
	}

	for(; q.size(); q.pop()){
		int x=q.front();
		// cout << "d[" << x << "] " << d[x] << "\n";
		for(int k:adj[x]){
			if(d[k]==-1) d[k]=d[x]+1, q.push(k);
		}
	}

	dfs(1, 0);

	cout << ans.size() << "\n";
	for(int x:ans) cout << x << " ";
}
// does it ever get lonely thinking you could live without me?
# Verdict Execution time Memory Grader output
1 Correct 183 ms 77400 KB Output is correct
2 Correct 209 ms 77864 KB Output is correct
3 Correct 202 ms 77768 KB Output is correct
4 Correct 274 ms 83508 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 12268 KB Output is correct
2 Correct 7 ms 12332 KB Output is correct
3 Correct 453 ms 39176 KB Output is correct
4 Correct 436 ms 41416 KB Output is correct
5 Correct 581 ms 38756 KB Output is correct
6 Correct 545 ms 42284 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 7 ms 12160 KB Output is correct
2 Correct 8 ms 12128 KB Output is correct
3 Correct 8 ms 12132 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 8 ms 12184 KB Output is correct
6 Correct 8 ms 12128 KB Output is correct
7 Correct 8 ms 12088 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 7 ms 12076 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 7 ms 12116 KB Output is correct
12 Correct 7 ms 12116 KB Output is correct
13 Correct 8 ms 12080 KB Output is correct
14 Correct 8 ms 12244 KB Output is correct
15 Correct 10 ms 12116 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 520 ms 39960 KB Output is correct
2 Correct 480 ms 39696 KB Output is correct
3 Correct 474 ms 42296 KB Output is correct
4 Correct 578 ms 38764 KB Output is correct
5 Correct 384 ms 37000 KB Output is correct
6 Correct 469 ms 47260 KB Output is correct
7 Correct 462 ms 45260 KB Output is correct
8 Correct 511 ms 44884 KB Output is correct
9 Correct 615 ms 38860 KB Output is correct
10 Correct 627 ms 38820 KB Output is correct
11 Correct 450 ms 40776 KB Output is correct
12 Correct 366 ms 43652 KB Output is correct
13 Correct 422 ms 45412 KB Output is correct
14 Correct 369 ms 42344 KB Output is correct
15 Correct 79 ms 16576 KB Output is correct
16 Correct 492 ms 36808 KB Output is correct
17 Correct 329 ms 37580 KB Output is correct
18 Correct 428 ms 33972 KB Output is correct
19 Correct 528 ms 45360 KB Output is correct
20 Correct 513 ms 50252 KB Output is correct
21 Correct 498 ms 38932 KB Output is correct
22 Correct 476 ms 39856 KB Output is correct