oj.uz

Submission #586836

# Submission time Handle Problem Language Result Execution time Memory
586836 2022-06-30T18:01:13 Z MetalPower Pastiri (COI20_pastiri) C++14
100 / 100
 737 ms 109708 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 223 ms 94280 KB Output is correct
2 Correct 279 ms 94744 KB Output is correct
3 Correct 276 ms 101380 KB Output is correct
4 Correct 339 ms 109708 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14548 KB Output is correct
2 Correct 9 ms 14600 KB Output is correct
3 Correct 441 ms 78396 KB Output is correct
4 Correct 431 ms 81148 KB Output is correct
5 Correct 619 ms 77828 KB Output is correct
6 Correct 727 ms 80096 KB Output is correct

Subtask #3
23.0 / 23.0

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

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 72356 KB Output is correct
2 Correct 559 ms 78828 KB Output is correct
3 Correct 638 ms 83608 KB Output is correct
4 Correct 604 ms 77788 KB Output is correct
5 Correct 528 ms 70720 KB Output is correct
6 Correct 631 ms 88548 KB Output is correct
7 Correct 722 ms 85900 KB Output is correct
8 Correct 727 ms 85128 KB Output is correct
9 Correct 737 ms 77896 KB Output is correct
10 Correct 615 ms 78020 KB Output is correct
11 Correct 434 ms 80520 KB Output is correct
12 Correct 437 ms 85892 KB Output is correct
13 Correct 481 ms 88112 KB Output is correct
14 Correct 380 ms 82404 KB Output is correct
15 Correct 57 ms 24900 KB Output is correct
16 Correct 655 ms 73104 KB Output is correct
17 Correct 446 ms 71164 KB Output is correct
18 Correct 632 ms 66588 KB Output is correct
19 Correct 671 ms 83508 KB Output is correct
20 Correct 701 ms 85704 KB Output is correct
21 Correct 642 ms 78040 KB Output is correct
22 Correct 576 ms 78524 KB Output is correct