oj.uz

Submission #581623

# Submission time Handle Problem Language Result Execution time Memory
581623 2022-06-22T22:21:39 Z penguinhacker Pastiri (COI20_pastiri) C++17
100 / 100
 539 ms 85032 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=5e5;
int n, k, d[mxN], dp[mxN], mark[mxN];
vector<int> adj[mxN], ans;

void dfs(int u=0, int p=-1) {
	mark[u]=-1;
	dp[u]=d[u]?-1:0;
	for (int v : adj[u])
		if (v!=p) {
			dfs(v, u);
			if (dp[v]!=-1)
				dp[u]=max(dp[u], dp[v]+1);
			mark[u]=max(mark[u], mark[v]-1);
		}
	if (dp[u]==-1||mark[u]>=dp[u]) { // this is covered
		dp[u]=-1;
		return;
	}
	//cout << u << " " << dp[u] << " " << mark[u] << endl;
	if (!u||(u&&dp[u]+1>d[p])) { // must place a pastir here
		dp[u]=-1;
		mark[u]=d[u];
		ans.push_back(u);	
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	memset(d, -1, sizeof(d));
	queue<int> q;
	for (int i=0; i<k; ++i) {
		int x;
		cin >> x, --x;
		d[x]=0;
		q.push(x);
	}
	for (; q.size(); q.pop()) {
		int u=q.front();
		for (int v : adj[u])
			if (d[v]==-1) {
				d[v]=d[u]+1;
				q.push(v);
			}
	}
	//for (int i=0; i<n; ++i)
	//	cout << d[i] << endl;
	dfs();
	cout << ans.size() << "\n";
	for (int i : ans)
		cout << i+1 << " ";
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 79228 KB Output is correct
2 Correct 197 ms 79404 KB Output is correct
3 Correct 201 ms 79324 KB Output is correct
4 Correct 257 ms 85032 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14292 KB Output is correct
2 Correct 9 ms 14164 KB Output is correct
3 Correct 399 ms 40700 KB Output is correct
4 Correct 426 ms 43060 KB Output is correct
5 Correct 529 ms 40296 KB Output is correct
6 Correct 529 ms 43684 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14036 KB Output is correct
2 Correct 9 ms 14056 KB Output is correct
3 Correct 8 ms 14036 KB Output is correct
4 Correct 8 ms 14008 KB Output is correct
5 Correct 8 ms 14140 KB Output is correct
6 Correct 12 ms 14140 KB Output is correct
7 Correct 8 ms 14144 KB Output is correct
8 Correct 9 ms 14036 KB Output is correct
9 Correct 8 ms 14136 KB Output is correct
10 Correct 8 ms 14036 KB Output is correct
11 Correct 8 ms 14036 KB Output is correct
12 Correct 8 ms 14036 KB Output is correct
13 Correct 9 ms 14036 KB Output is correct
14 Correct 8 ms 14164 KB Output is correct
15 Correct 8 ms 14140 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 41316 KB Output is correct
2 Correct 505 ms 41128 KB Output is correct
3 Correct 475 ms 43780 KB Output is correct
4 Correct 513 ms 40156 KB Output is correct
5 Correct 382 ms 38584 KB Output is correct
6 Correct 463 ms 48628 KB Output is correct
7 Correct 462 ms 46832 KB Output is correct
8 Correct 473 ms 46460 KB Output is correct
9 Correct 539 ms 40452 KB Output is correct
10 Correct 529 ms 40312 KB Output is correct
11 Correct 368 ms 42176 KB Output is correct
12 Correct 334 ms 45192 KB Output is correct
13 Correct 391 ms 46916 KB Output is correct
14 Correct 313 ms 43724 KB Output is correct
15 Correct 43 ms 18380 KB Output is correct
16 Correct 480 ms 38392 KB Output is correct
17 Correct 315 ms 39036 KB Output is correct
18 Correct 399 ms 35512 KB Output is correct
19 Correct 501 ms 46916 KB Output is correct
20 Correct 514 ms 51672 KB Output is correct
21 Correct 474 ms 40460 KB Output is correct
22 Correct 486 ms 41068 KB Output is correct