oj.uz

Submission #768596

# Submission time Handle Problem Language Result Execution time Memory
768596 2023-06-28T09:40:17 Z flappybird Pastiri (COI20_pastiri) C++17
100 / 100
 802 ms 83232 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 500101
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<int> adj[MAX];
int dis[MAX];
int sheep[MAX];
vector<int> v;
int vis[MAX];
int dep[MAX];
int prt[MAX];
void dfs(int x, int p = 0) {
	if (sheep[x]) dis[x] = 0;
	else dis[x] = 10101010;
	prt[x] = p;
	for (auto v : adj[x]) {
		if (v == p) continue;
		dep[v] = dep[x] + 1;
		dfs(v, x);
		dis[x] = min(dis[x], dis[v] + 1);
	}
}
void down(int x, int p = 0) {
	for (auto v : adj[x]) if (v != p) {
		dis[v] = min(dis[v], dis[x] + 1);
		down(v, x);
	}
}
int memo[MAX];
void chk(int x, int d, int p = 0) {
	sheep[x] = 0;
	if (d <= memo[x]) return;
	memo[x] = max(memo[x], d);
	for (auto v : adj[x]) if (v != p) chk(v, d - 1, x);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, K;
	cin >> N >> K;
	int i, a, b;
	for (i = 1; i < N; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	vector<int> sv;
	for (i = 1; i <= K; i++) {
		cin >> a;
		sv.push_back(a);
		sheep[a] = 1;
	}
	dfs(1);
	down(1);
	sort(sv.begin(), sv.end(), [&](int a, int b) {return dep[a] > dep[b]; });
	int cnt = 0;
	vector<int> ans;
	for (i = 1; i <= N; i++) vis[i] = 0;
	for (auto x : sv) {
		if (!sheep[x]) continue;
		cnt++;
		int v = x;
		while (1) {
			int p = prt[v];
			if (!p) break;
			if (dis[p] < dep[x] - dep[p]) break;
			v = p;
			//if (vis[v]) break;
		}
		ans.push_back(v);
		chk(v, dis[v]);
	}
	cout << ans.size() << ln;
	for (auto v : ans) cout << v << bb;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 75292 KB Output is correct
2 Correct 137 ms 78056 KB Output is correct
3 Correct 143 ms 78432 KB Output is correct
4 Correct 214 ms 83232 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12372 KB Output is correct
2 Correct 6 ms 12388 KB Output is correct
3 Correct 323 ms 39416 KB Output is correct
4 Correct 294 ms 41772 KB Output is correct
5 Correct 469 ms 39560 KB Output is correct
6 Correct 635 ms 42956 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12116 KB Output is correct
2 Correct 5 ms 12116 KB Output is correct
3 Correct 5 ms 12200 KB Output is correct
4 Correct 6 ms 12116 KB Output is correct
5 Correct 6 ms 12244 KB Output is correct
6 Correct 6 ms 12164 KB Output is correct
7 Correct 6 ms 12116 KB Output is correct
8 Correct 6 ms 12116 KB Output is correct
9 Correct 6 ms 12116 KB Output is correct
10 Correct 6 ms 12116 KB Output is correct
11 Correct 5 ms 12116 KB Output is correct
12 Correct 5 ms 12176 KB Output is correct
13 Correct 6 ms 12156 KB Output is correct
14 Correct 6 ms 12244 KB Output is correct
15 Correct 6 ms 12244 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 40424 KB Output is correct
2 Correct 440 ms 40288 KB Output is correct
3 Correct 561 ms 41968 KB Output is correct
4 Correct 499 ms 39228 KB Output is correct
5 Correct 367 ms 36788 KB Output is correct
6 Correct 441 ms 46284 KB Output is correct
7 Correct 443 ms 44916 KB Output is correct
8 Correct 497 ms 44828 KB Output is correct
9 Correct 802 ms 39680 KB Output is correct
10 Correct 530 ms 46156 KB Output is correct
11 Correct 315 ms 47564 KB Output is correct
12 Correct 256 ms 51000 KB Output is correct
13 Correct 298 ms 52644 KB Output is correct
14 Correct 304 ms 48800 KB Output is correct
15 Correct 35 ms 17940 KB Output is correct
16 Correct 611 ms 43696 KB Output is correct
17 Correct 308 ms 43732 KB Output is correct
18 Correct 499 ms 39936 KB Output is correct
19 Correct 439 ms 52816 KB Output is correct
20 Correct 504 ms 57572 KB Output is correct
21 Correct 464 ms 46252 KB Output is correct
22 Correct 498 ms 46924 KB Output is correct