Submission #236031

#	Time	Username	Problem	Language	Result	Execution time	Memory
236031		JustasZ	Tax Evasion (LMIO19_mokesciai)	C++14	100 / 100	126 ms	28396 KiB

mokesciai

/*input
7 2
1
2
3
3
5
6
3 4
*/
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, m, has[maxn], dep[maxn], need[maxn], cnt[maxn], par[maxn];
vector<int>stk, ord;
vector<int>adj[maxn];
void prep(int v) {
	stk.pb(v);
	if (has[v]) {
		++need[stk[dep[v] / 2 + 1]];
	}
	for (int to : adj[v]) {
		prep(to);
	}
	stk.pop_back();
}
bool can(int min_dep) {
	for (int v : ord) {
		if (dep[v] >= min_dep) {
			cnt[v]--;
		}
		if (cnt[v] > 0) {
			return false;
		}
		cnt[par[v]] += cnt[v];
	}
	return true;
}
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for (int i = 2; i <= n; i++) {
		int p;
		cin >> p;
		dep[i] = dep[p] + 1;
		par[i] = p;
		adj[p].pb(i);
	}

	for (int i = 1; i <= m; i++) {
		int v;
		cin >> v;
		has[v] = 1;
	}

	for (int i = 1; i <= n; i++) {
		ord.pb(i);
	}
	sort(all(ord), [&](int i, int j) {
		return dep[i] > dep[j];
	});

	prep(1);
	int lo = 0, hi = n - 1;
	while (lo < hi) {
		int mid = (lo + hi + 1) / 2;

		for (int i = 1; i <= n; i++) {
			cnt[i] = need[i];
		}

		if (can(mid)) {
			lo = mid;
		} else {
			hi = mid - 1;
		}
	}

	cout << lo + 1 << "\n";
	return 0;
}

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