Submission #254017

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
254017	2020-07-29T09:10:50 Z	maximath_1	Tax Evasion (LMIO19_mokesciai)	C++11	100 / 100	231 ms	47580 KB

mokesciai

/*
	* LMIO 2019 Tax Evasion
	* Main Idea : Euler tour, binary search the answer
	* If there's a coin at depth d, it can only climb to
	* floor((d - 1) / 2), as Just will get caught afterwards
	* So we can build an euler tour, coin X can only stay at
	* a range L to R
	* Binary search the answer: if a is a candidate answer, 
	* all coins should have depth at least a - 1
	* Check if >= a possible using greedy
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m, timer;
int par[18][200005], depth[200005], lf[200005], rg[200005];
bool is_coin[200005];
vector<int> adj[200005], que[200005], order;

void euler_tour(int nw){
	order.push_back(nw);
	lf[nw] = timer ++;
	for(int nx : adj[nw])
		euler_tour(nx);
	rg[nw] = timer;
}

int anc(int nw, int dp){
	for(int i = 17; i >= 0; i --)
		if(dp & (1 << i)) nw = par[i][nw];
	return nw;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for(int p, i = 2; i <= n; i ++){
		cin >> p;
		par[0][i] = p;
		depth[i] = depth[p] + 1;
		adj[p].push_back(i);
	}

	for(int i = 1; i < 18; i ++) for(int j = 1; j <= n; j ++)
		par[i][j] = par[i - 1][par[i - 1][j]];

	for(int p, i = 0; i < m; i ++){
		cin >> p;
		is_coin[p] = true;
	}

	euler_tour(1);
	
	for(int i = 1; i <= n; i ++) if(is_coin[i]){
		int up = anc(i, (depth[i] - 1) / 2);
		que[lf[up]].push_back(rg[up]);
	}

	int res = 0;
	for(int l = 0, r = n, md; l <= r; ){
		md = (l + r) / 2;
		priority_queue<int, vector<int>, greater<int> > pq;
		bool can = true;

		for(int i = 0; i < n && can; i ++){
			for(int j : que[i]) pq.push(j);
			if(depth[order[i]] >= md && !pq.empty()){
				int nw = pq.top(); pq.pop();
				if(nw <= i) can = false;
			}
		}

		if(!pq.empty()) can = false;

		if(can){
			res = md; l = md + 1;
		}else{
			r = md - 1;
		}
	}

	cout << res + 1 << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9856 KB	Output is correct
2	Correct	5 ms	9856 KB	Output is correct
3	Correct	8 ms	10752 KB	Output is correct
4	Correct	9 ms	10752 KB	Output is correct
5	Correct	8 ms	10752 KB	Output is correct
6	Correct	73 ms	42732 KB	Output is correct
7	Correct	77 ms	42732 KB	Output is correct
8	Correct	7 ms	10752 KB	Output is correct
9	Correct	184 ms	47304 KB	Output is correct
10	Correct	217 ms	47580 KB	Output is correct
11	Correct	146 ms	45272 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9856 KB	Output is correct
2	Correct	7 ms	10496 KB	Output is correct
3	Correct	6 ms	10496 KB	Output is correct
4	Correct	7 ms	10368 KB	Output is correct
5	Correct	7 ms	10496 KB	Output is correct
6	Correct	7 ms	10368 KB	Output is correct
7	Correct	73 ms	42732 KB	Output is correct
8	Correct	77 ms	42732 KB	Output is correct
9	Correct	7 ms	10752 KB	Output is correct
10	Correct	61 ms	34884 KB	Output is correct
11	Correct	61 ms	34984 KB	Output is correct
12	Correct	77 ms	29836 KB	Output is correct
13	Correct	70 ms	36204 KB	Output is correct
14	Correct	66 ms	30316 KB	Output is correct
15	Correct	71 ms	29936 KB	Output is correct
16	Correct	72 ms	36204 KB	Output is correct
17	Correct	98 ms	30576 KB	Output is correct
18	Correct	69 ms	39152 KB	Output is correct
19	Correct	69 ms	34160 KB	Output is correct
20	Correct	66 ms	33780 KB	Output is correct
21	Correct	72 ms	33648 KB	Output is correct
22	Correct	75 ms	33776 KB	Output is correct
23	Correct	69 ms	33136 KB	Output is correct
24	Correct	65 ms	33524 KB	Output is correct

Subtask #3
39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9856 KB	Output is correct
2	Correct	6 ms	9856 KB	Output is correct
3	Correct	5 ms	9856 KB	Output is correct
4	Correct	6 ms	9856 KB	Output is correct
5	Correct	6 ms	9856 KB	Output is correct
6	Correct	7 ms	10496 KB	Output is correct
7	Correct	7 ms	10496 KB	Output is correct
8	Correct	8 ms	10496 KB	Output is correct
9	Correct	10 ms	10368 KB	Output is correct
10	Correct	10 ms	10368 KB	Output is correct
11	Correct	10 ms	10496 KB	Output is correct
12	Correct	7 ms	10368 KB	Output is correct
13	Correct	9 ms	10496 KB	Output is correct
14	Correct	7 ms	10368 KB	Output is correct
15	Correct	8 ms	10624 KB	Output is correct
16	Correct	9 ms	10624 KB	Output is correct
17	Correct	8 ms	10496 KB	Output is correct
18	Correct	11 ms	10624 KB	Output is correct
19	Correct	9 ms	10496 KB	Output is correct
20	Correct	11 ms	10368 KB	Output is correct
21	Correct	8 ms	10368 KB	Output is correct
22	Correct	6 ms	9856 KB	Output is correct
23	Correct	5 ms	9856 KB	Output is correct
24	Correct	8 ms	10752 KB	Output is correct
25	Correct	9 ms	10752 KB	Output is correct
26	Correct	8 ms	10752 KB	Output is correct
27	Correct	6 ms	9856 KB	Output is correct
28	Correct	7 ms	10496 KB	Output is correct
29	Correct	6 ms	10496 KB	Output is correct
30	Correct	7 ms	10368 KB	Output is correct
31	Correct	7 ms	10496 KB	Output is correct
32	Correct	7 ms	10368 KB	Output is correct
33	Correct	7 ms	10752 KB	Output is correct

Subtask #4
29.0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	9856 KB	Output is correct
2	Correct	6 ms	9856 KB	Output is correct
3	Correct	5 ms	9856 KB	Output is correct
4	Correct	6 ms	9856 KB	Output is correct
5	Correct	6 ms	9856 KB	Output is correct
6	Correct	7 ms	10496 KB	Output is correct
7	Correct	7 ms	10496 KB	Output is correct
8	Correct	8 ms	10496 KB	Output is correct
9	Correct	10 ms	10368 KB	Output is correct
10	Correct	10 ms	10368 KB	Output is correct
11	Correct	10 ms	10496 KB	Output is correct
12	Correct	7 ms	10368 KB	Output is correct
13	Correct	9 ms	10496 KB	Output is correct
14	Correct	7 ms	10368 KB	Output is correct
15	Correct	8 ms	10624 KB	Output is correct
16	Correct	9 ms	10624 KB	Output is correct
17	Correct	8 ms	10496 KB	Output is correct
18	Correct	11 ms	10624 KB	Output is correct
19	Correct	9 ms	10496 KB	Output is correct
20	Correct	11 ms	10368 KB	Output is correct
21	Correct	8 ms	10368 KB	Output is correct
22	Correct	6 ms	9856 KB	Output is correct
23	Correct	5 ms	9856 KB	Output is correct
24	Correct	8 ms	10752 KB	Output is correct
25	Correct	9 ms	10752 KB	Output is correct
26	Correct	8 ms	10752 KB	Output is correct
27	Correct	6 ms	9856 KB	Output is correct
28	Correct	7 ms	10496 KB	Output is correct
29	Correct	6 ms	10496 KB	Output is correct
30	Correct	7 ms	10368 KB	Output is correct
31	Correct	7 ms	10496 KB	Output is correct
32	Correct	7 ms	10368 KB	Output is correct
33	Correct	73 ms	42732 KB	Output is correct
34	Correct	77 ms	42732 KB	Output is correct
35	Correct	7 ms	10752 KB	Output is correct
36	Correct	61 ms	34884 KB	Output is correct
37	Correct	61 ms	34984 KB	Output is correct
38	Correct	77 ms	29836 KB	Output is correct
39	Correct	70 ms	36204 KB	Output is correct
40	Correct	66 ms	30316 KB	Output is correct
41	Correct	71 ms	29936 KB	Output is correct
42	Correct	72 ms	36204 KB	Output is correct
43	Correct	98 ms	30576 KB	Output is correct
44	Correct	69 ms	39152 KB	Output is correct
45	Correct	69 ms	34160 KB	Output is correct
46	Correct	66 ms	33780 KB	Output is correct
47	Correct	72 ms	33648 KB	Output is correct
48	Correct	75 ms	33776 KB	Output is correct
49	Correct	69 ms	33136 KB	Output is correct
50	Correct	65 ms	33524 KB	Output is correct
51	Correct	184 ms	47304 KB	Output is correct
52	Correct	217 ms	47580 KB	Output is correct
53	Correct	146 ms	45272 KB	Output is correct
54	Correct	86 ms	35480 KB	Output is correct
55	Correct	80 ms	35480 KB	Output is correct
56	Correct	145 ms	37812 KB	Output is correct
57	Correct	146 ms	31644 KB	Output is correct
58	Correct	84 ms	29804 KB	Output is correct
59	Correct	231 ms	34752 KB	Output is correct
60	Correct	195 ms	32028 KB	Output is correct
61	Correct	195 ms	39620 KB	Output is correct
62	Correct	143 ms	31912 KB	Output is correct
63	Correct	116 ms	40808 KB	Output is correct
64	Correct	111 ms	35320 KB	Output is correct
65	Correct	83 ms	34668 KB	Output is correct
66	Correct	87 ms	35680 KB	Output is correct
67	Correct	98 ms	35448 KB	Output is correct
68	Correct	110 ms	34656 KB	Output is correct
69	Correct	130 ms	37308 KB	Output is correct
70	Correct	71 ms	21900 KB	Output is correct
71	Correct	120 ms	35636 KB	Output is correct

Submission #254017

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 22.0 / 22.0

Subtask #3 39.0 / 39.0

Subtask #4 29.0 / 29.0

Subtask #1
10.0 / 10.0

Subtask #2
22.0 / 22.0

Subtask #3
39.0 / 39.0

Subtask #4
29.0 / 29.0