oj.uz

Submission #586845

# Submission time Handle Problem Language Result Execution time Memory
586845 2022-06-30T18:07:11 Z MetalPower Pastiri (COI20_pastiri) C++14
100 / 100
 801 ms 101092 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 5e5 + 10;
const int LG = 20;
const int INF = 1e9 + 7;

int N, K, dep[MX], sp[MX][LG];
vector<int> adj[MX];
vector<pii> s;

void dfs(int u, int v){

	dep[u] = dep[v] + 1;
	sp[u][0] = v;

	for(int nxt : adj[u]){
		if(nxt == v) continue;
		dfs(nxt, u);
	}
}

int dt[MX];
bool used[MX];

void bfs(){

	for(int i = 0; i < MX; i++) dt[i] = INF;

	queue<pii> q;
	for(pii x : s){
		dt[x.se] = 0;
		q.push({0, x.se});
	}

	while(!q.empty()){

		int cd = q.front().fi, cr = q.front().se;
		q.pop();

		for(int nxt : adj[cr]){
			if(dt[nxt] > cd + 1){
				dt[nxt] = cd + 1;
				q.push({dt[nxt], nxt});
			}
		}
	}
}

void mark(int u, int ndist){

	if(dt[u] == ndist) used[u] = 1;
	else return;

	for(int nxt : adj[u]){
		if(used[nxt]) continue;
		mark(nxt, ndist - 1);
	}
}

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

	cin >> N >> K;

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

	dfs(1, 0);

	for(int i = 1; i <= K; i++){
		int u; cin >> u;
		s.push_back({dep[u], u});
	}

	for(int k = 1; k < LG; k++){
		for(int i = 1; i <= N; i++){
			sp[i][k] = sp[sp[i][k - 1]][k - 1];
		}
	}

	sort(s.begin(), s.end(), greater<pii>());

	bfs();

	vector<int> ans;

	for(int i = 0; i < K; i++){

		int u = s[i].se, dist = 0;

		if(used[u]) continue;

		for(int k = LG - 1; k >= 0; k--){
			if(sp[u][k] != 0 && dt[sp[u][k]] == (dist + (1 << k))){
				u = sp[u][k], dist += 1 << k;
			}
		}

		ans.push_back(u);
		mark(u, dt[u]);
	}

	cout << ans.size() << '\n';
	for(int x : ans) cout << x << " ";
	cout << '\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 94244 KB Output is correct
2 Correct 274 ms 94636 KB Output is correct
3 Correct 302 ms 94640 KB Output is correct
4 Correct 357 ms 101092 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14568 KB Output is correct
2 Correct 10 ms 14540 KB Output is correct
3 Correct 498 ms 71760 KB Output is correct
4 Correct 504 ms 74632 KB Output is correct
5 Correct 677 ms 71248 KB Output is correct
6 Correct 801 ms 73356 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14164 KB Output is correct
2 Correct 9 ms 14164 KB Output is correct
3 Correct 10 ms 14288 KB Output is correct
4 Correct 8 ms 14164 KB Output is correct
5 Correct 9 ms 14292 KB Output is correct
6 Correct 8 ms 14292 KB Output is correct
7 Correct 8 ms 14164 KB Output is correct
8 Correct 8 ms 14164 KB Output is correct
9 Correct 10 ms 14164 KB Output is correct
10 Correct 10 ms 14168 KB Output is correct
11 Correct 11 ms 14164 KB Output is correct
12 Correct 8 ms 14164 KB Output is correct
13 Correct 11 ms 14164 KB Output is correct
14 Correct 8 ms 14292 KB Output is correct
15 Correct 9 ms 14292 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 72276 KB Output is correct
2 Correct 665 ms 72084 KB Output is correct
3 Correct 742 ms 75560 KB Output is correct
4 Correct 651 ms 71092 KB Output is correct
5 Correct 543 ms 64132 KB Output is correct
6 Correct 695 ms 79976 KB Output is correct
7 Correct 753 ms 77752 KB Output is correct
8 Correct 701 ms 77172 KB Output is correct
9 Correct 716 ms 71400 KB Output is correct
10 Correct 638 ms 71264 KB Output is correct
11 Correct 426 ms 73924 KB Output is correct
12 Correct 385 ms 77884 KB Output is correct
13 Correct 449 ms 79460 KB Output is correct
14 Correct 376 ms 75772 KB Output is correct
15 Correct 64 ms 23876 KB Output is correct
16 Correct 641 ms 66892 KB Output is correct
17 Correct 461 ms 64704 KB Output is correct
18 Correct 575 ms 60976 KB Output is correct
19 Correct 641 ms 76384 KB Output is correct
20 Correct 668 ms 78704 KB Output is correct
21 Correct 541 ms 71468 KB Output is correct
22 Correct 563 ms 71860 KB Output is correct