Submission #249896

#	Time	Username	Problem	Language	Result	Execution time	Memory
249896		dimash241	Tax Evasion (LMIO19_mokesciai)	C++17	100 / 100	239 ms	53352 KiB

mokesciai

#include <queue>
#include <vector>
#include <iostream>
#include <functional>
using namespace std;
int solve(int N, int K, vector<int> S, vector<int> V) {
	int bits = 1;
	while ((1 << bits) <= N) ++bits;
	vector<vector<int> > P(bits, vector<int>(N));
	vector<int> depth(N);
	vector<vector<int> > G(N);
	for (int i = 1; i < N; ++i) {
		P[0][i] = S[i - 1];
		depth[i] = depth[P[0][i]] + 1;
		G[P[0][i]].push_back(i);
	}
	vector<bool> coin(N);
	for (int i = 0; i < K; ++i) {
		coin[V[i]] = true;
	}
	for (int i = 1; i < bits; ++i) {
		for (int j = 0; j < N; ++j) {
			P[i][j] = P[i - 1][P[i - 1][j]];
		}
	}
	int cnt = 0;
	vector<int> sl(N), sr(N), ord;
	function<void(int)> eulertour = [&](int pos) {
		ord.push_back(pos);
		sl[pos] = cnt++;
		for (int i : G[pos]) {
			eulertour(i);
		}
		sr[pos] = cnt;
	};
	function<int(int, int)> ancestor = [&](int pos, int level) {
		for (int i = bits - 1; i >= 0; --i) {
			if (level >= (1 << i)) {
				pos = P[i][pos];
				level -= (1 << i);
			}
		}
		return pos;
	};
	eulertour(0);
	if (coin[0]) return 1;
	int L = 0, R = N + 1;
  	vector<vector<int> > query(N);
	for (int i = 1; i < N; ++i) {
		if (!coin[i]) continue;
		int pos = ancestor(i, (depth[i] - 1) / 2);
		query[sl[pos]].push_back(sr[pos]);
	}
	while (R - L > 1) {
		int M = (L + R) >> 1;
		
		priority_queue<int, vector<int>, greater<int> > que;
		bool ok = true;
		for (int i = 0; i < N && ok; ++i) {
			for (int j : query[i]) {
				que.push(j);
			}
			if (depth[ord[i]] >= M && !que.empty()) {
				int u = que.top(); que.pop();
				if (u <= i) ok = false;
			}
		}
		if (!que.empty()) ok = false;
		if (ok) L = M;
		else R = M;
	}
	return R;
}
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	vector<int> S(N - 1);
	for (int i = 0; i < N - 1; ++i) {
		cin >> S[i]; --S[i];
	}
	vector<int> V(K);
	for (int i = 0; i < K; ++i) {
		cin >> V[i]; --V[i];
	}
	int ans = solve(N, K, S, V);
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 39 / 39
• Subtask 4: 29 / 29