oj.uz

Submission #586842

# Submission time Handle Problem Language Result Execution time Memory
586842 2022-06-30T18:05:41 Z MetalPower Pastiri (COI20_pastiri) C++14
0 / 100
 583 ms 94844 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;

		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;
			}
		}

		if(!used[u]){
			ans.push_back(u);
			mark(u, dt[u]);
		}
	}

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 94300 KB Output is correct
2 Incorrect 273 ms 94844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 14164 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 583 ms 72320 KB Output isn't correct
2 Halted 0 ms 0 KB -