Submission #253986

#	Time	Username	Problem	Language	Result	Execution time	Memory
253986		Berted	Tax Evasion (LMIO19_mokesciai)	C++14	100 / 100	190 ms	47088 KiB

mokesciai

#include <iostream>
#include <set>
#include <vector>
#include <assert.h>
#include <map>
#include <list>
#define vi vector<int>
#define pub push_back
#define pii pair<int, int>
#define fst first
#define snd second
using namespace std;

int n, k, cnt[200001] = {}, mn = 1e9;
bool spc[200001];
vector<int> adj[200001];
vi par;

void dfs(int u, int p)
{
	int h = par.size();
	par.push_back(u);
	cnt[par[h / 2 + 1]] += spc[u];
	spc[u] = 0;
	for (auto v : adj[u])
	{
		// cout << u << " - " << v << "\n";
		if (v != p) dfs(v, u);
	}
	par.pop_back();
}


map<int, int>* dfs2(int u, int p, int h)
{
	map<int, int> *ret = nullptr, *rr;
	
	for (auto v : adj[u])
	{
		if (v != p)
		{
			rr = dfs2(v, u, h + 1);
			if (ret == nullptr || rr -> size() > ret -> size()) {swap(rr, ret);}
			if (rr != nullptr) for (auto v : *rr) {(*ret)[v.fst] += v.snd;}
		}
	}
	if (ret == nullptr) {ret = new map<int, int>;}
	(*ret)[-h]++;
	for (int i = 0; i < cnt[u]; i++)
	{
		mn = min(mn, -(ret -> begin() -> fst));
		(ret -> begin() -> snd)--;
		if (ret -> begin() -> snd == 0) {ret -> erase(ret -> begin());}
	}
	return ret;
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i < n; i++)
	{
		int v; cin >> v;
		adj[v - 1].push_back(i);
		adj[i].push_back(v - 1);
	}
	for (int i = 0; i < k; i++)
	{
		int x; cin >> x; spc[x - 1] = 1;
	}
	if (spc[0]) {cout << "1\n";}
	else
	{
		dfs(0, -1); dfs2(0 ,-1, 0);
		cout << mn + 1 << '\n';
	}
	
	return 0;
}

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