Submission #255086

#	Time	Username	Problem	Language	Result	Execution time	Memory
255086		vioalbert	Tax Evasion (LMIO19_mokesciai)	C++14	100 / 100	273 ms	55528 KiB

mokesciai

#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 / 10
• Subtask 2: 22 / 22
• Subtask 3: 39 / 39
• Subtask 4: 29 / 29