oj.uz

Submission #255086

# Submission time Handle Problem Language Result Execution time Memory
255086 2020-07-31T08:53:38 Z vioalbert Tax Evasion (LMIO19_mokesciai) C++14
100 / 100
 273 ms 55528 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5+5;
int n, m;
vector<int> adj[N];
bool coin[N];

void read() {
	cin >> n >> m;
	for(int i = 2; i <= n; i++) {
		int x; cin >> x;
		adj[x].push_back(i);
		adj[i].push_back(x);
	}
	memset(coin, 0, sizeof coin);
	for(int i = 0; i < m; i++) {
		int x; cin >> x;
		coin[x] = 1;
	}
}

const int lv = 20;
int par[N][lv+1];
int fi[N], se[N], depth[N];
vector<int> euler;
int timer;

void dfs(int u, int p, int h) {
	euler.push_back(u);
	fi[u] = timer++;
	depth[u] = h;
	par[u][0] = p;
	for(int i = 1; i <= lv; i++)
		par[u][i] = par[par[u][i-1]][i-1];
	for(int v : adj[u]) if(v != p)
		dfs(v, u, h+1);
	se[u] = timer;
}

int ancestor(int u, int x) {
	for(int i = lv; i >= 0; i--) {
		if(x - (1<<i) >= 0)
			u = par[u][i], x -= (1<<i);
	}
	return u;
}

void solve() {
	if(coin[1]) {
		cout << 1 << '\n';
		return;
	}
	timer = 0;
	dfs(1, 1, 0);

	vector<vector<int>> queries(n+1);
	for(int i = 1; i <= n; i++) {
		if(!coin[i]) continue;
		int anc = ancestor(i, (depth[i] - 1) / 2);
		queries[fi[anc]].push_back(se[anc]);
	}

	int ans = 0;
	int l = 0, r = n;
	while(l <= r) {
		int mid = (l+r)/2;
		bool ok = 1;
		priority_queue<int, vector<int>, greater<int>> pq;
		for(int i = 0; i < n && ok; i++) {
			for(int j : queries[i])
				pq.push(j);
			if(depth[euler[i]] >= mid && !pq.empty()) {
				int x = pq.top(); pq.pop();
				if(x <= i) ok = 0;
			}
		}
		if(!pq.empty()) ok = 0;
		if(ok) {
			ans = mid, l = mid + 1;
		} else {
			r = mid - 1;
		}
	}

	cout << ans + 1 << '\n';
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	read();
	solve();
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5248 KB Output is correct
2 Correct 3 ms 5248 KB Output is correct
3 Correct 7 ms 6400 KB Output is correct
4 Correct 8 ms 6528 KB Output is correct
5 Correct 7 ms 6400 KB Output is correct
6 Correct 104 ms 49640 KB Output is correct
7 Correct 104 ms 49644 KB Output is correct
8 Correct 6 ms 6400 KB Output is correct
9 Correct 230 ms 54892 KB Output is correct
10 Correct 258 ms 55528 KB Output is correct
11 Correct 182 ms 52684 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5248 KB Output is correct
2 Correct 5 ms 6144 KB Output is correct
3 Correct 5 ms 6144 KB Output is correct
4 Correct 5 ms 6016 KB Output is correct
5 Correct 5 ms 6144 KB Output is correct
6 Correct 6 ms 6016 KB Output is correct
7 Correct 104 ms 49640 KB Output is correct
8 Correct 104 ms 49644 KB Output is correct
9 Correct 6 ms 6400 KB Output is correct
10 Correct 102 ms 42600 KB Output is correct
11 Correct 92 ms 42600 KB Output is correct
12 Correct 130 ms 37220 KB Output is correct
13 Correct 115 ms 43372 KB Output is correct
14 Correct 104 ms 37100 KB Output is correct
15 Correct 152 ms 37228 KB Output is correct
16 Correct 127 ms 43500 KB Output is correct
17 Correct 178 ms 37232 KB Output is correct
18 Correct 102 ms 44780 KB Output is correct
19 Correct 115 ms 37996 KB Output is correct
20 Correct 114 ms 37352 KB Output is correct
21 Correct 118 ms 37356 KB Output is correct
22 Correct 117 ms 37356 KB Output is correct
23 Correct 98 ms 37104 KB Output is correct
24 Correct 120 ms 37228 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5248 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 3 ms 5248 KB Output is correct
4 Correct 3 ms 5248 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 5 ms 6220 KB Output is correct
7 Correct 8 ms 6144 KB Output is correct
8 Correct 7 ms 6272 KB Output is correct
9 Correct 6 ms 6144 KB Output is correct
10 Correct 5 ms 6016 KB Output is correct
11 Correct 6 ms 6272 KB Output is correct
12 Correct 7 ms 6144 KB Output is correct
13 Correct 7 ms 6252 KB Output is correct
14 Correct 8 ms 6144 KB Output is correct
15 Correct 7 ms 6272 KB Output is correct
16 Correct 7 ms 6272 KB Output is correct
17 Correct 6 ms 6144 KB Output is correct
18 Correct 8 ms 6400 KB Output is correct
19 Correct 6 ms 6144 KB Output is correct
20 Correct 6 ms 6016 KB Output is correct
21 Correct 5 ms 5888 KB Output is correct
22 Correct 3 ms 5248 KB Output is correct
23 Correct 3 ms 5248 KB Output is correct
24 Correct 7 ms 6400 KB Output is correct
25 Correct 8 ms 6528 KB Output is correct
26 Correct 7 ms 6400 KB Output is correct
27 Correct 3 ms 5248 KB Output is correct
28 Correct 5 ms 6144 KB Output is correct
29 Correct 5 ms 6144 KB Output is correct
30 Correct 5 ms 6016 KB Output is correct
31 Correct 5 ms 6144 KB Output is correct
32 Correct 6 ms 6016 KB Output is correct
33 Correct 6 ms 6400 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5248 KB Output is correct
2 Correct 4 ms 5248 KB Output is correct
3 Correct 3 ms 5248 KB Output is correct
4 Correct 3 ms 5248 KB Output is correct
5 Correct 4 ms 5248 KB Output is correct
6 Correct 5 ms 6220 KB Output is correct
7 Correct 8 ms 6144 KB Output is correct
8 Correct 7 ms 6272 KB Output is correct
9 Correct 6 ms 6144 KB Output is correct
10 Correct 5 ms 6016 KB Output is correct
11 Correct 6 ms 6272 KB Output is correct
12 Correct 7 ms 6144 KB Output is correct
13 Correct 7 ms 6252 KB Output is correct
14 Correct 8 ms 6144 KB Output is correct
15 Correct 7 ms 6272 KB Output is correct
16 Correct 7 ms 6272 KB Output is correct
17 Correct 6 ms 6144 KB Output is correct
18 Correct 8 ms 6400 KB Output is correct
19 Correct 6 ms 6144 KB Output is correct
20 Correct 6 ms 6016 KB Output is correct
21 Correct 5 ms 5888 KB Output is correct
22 Correct 3 ms 5248 KB Output is correct
23 Correct 3 ms 5248 KB Output is correct
24 Correct 7 ms 6400 KB Output is correct
25 Correct 8 ms 6528 KB Output is correct
26 Correct 7 ms 6400 KB Output is correct
27 Correct 3 ms 5248 KB Output is correct
28 Correct 5 ms 6144 KB Output is correct
29 Correct 5 ms 6144 KB Output is correct
30 Correct 5 ms 6016 KB Output is correct
31 Correct 5 ms 6144 KB Output is correct
32 Correct 6 ms 6016 KB Output is correct
33 Correct 104 ms 49640 KB Output is correct
34 Correct 104 ms 49644 KB Output is correct
35 Correct 6 ms 6400 KB Output is correct
36 Correct 102 ms 42600 KB Output is correct
37 Correct 92 ms 42600 KB Output is correct
38 Correct 130 ms 37220 KB Output is correct
39 Correct 115 ms 43372 KB Output is correct
40 Correct 104 ms 37100 KB Output is correct
41 Correct 152 ms 37228 KB Output is correct
42 Correct 127 ms 43500 KB Output is correct
43 Correct 178 ms 37232 KB Output is correct
44 Correct 102 ms 44780 KB Output is correct
45 Correct 115 ms 37996 KB Output is correct
46 Correct 114 ms 37352 KB Output is correct
47 Correct 118 ms 37356 KB Output is correct
48 Correct 117 ms 37356 KB Output is correct
49 Correct 98 ms 37104 KB Output is correct
50 Correct 120 ms 37228 KB Output is correct
51 Correct 230 ms 54892 KB Output is correct
52 Correct 258 ms 55528 KB Output is correct
53 Correct 182 ms 52684 KB Output is correct
54 Correct 120 ms 43236 KB Output is correct
55 Correct 117 ms 43160 KB Output is correct
56 Correct 172 ms 46720 KB Output is correct
57 Correct 133 ms 38980 KB Output is correct
58 Correct 123 ms 37088 KB Output is correct
59 Correct 273 ms 42052 KB Output is correct
60 Correct 178 ms 39808 KB Output is correct
61 Correct 171 ms 47812 KB Output is correct
62 Correct 201 ms 39160 KB Output is correct
63 Correct 160 ms 46828 KB Output is correct
64 Correct 158 ms 39328 KB Output is correct
65 Correct 126 ms 38508 KB Output is correct
66 Correct 137 ms 39836 KB Output is correct
67 Correct 147 ms 39772 KB Output is correct
68 Correct 143 ms 39204 KB Output is correct
69 Correct 166 ms 41624 KB Output is correct
70 Correct 92 ms 23564 KB Output is correct
71 Correct 149 ms 41780 KB Output is correct