Submission #843829

#	Time	Username	Problem	Language	Result	Execution time	Memory
843829		denniskim	Beech Tree (IOI23_beechtree)	C++17	100 / 100	195 ms	96532 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>

using namespace std;
typedef int ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

vector<ll> zip;
vector<ll> vec[200010];
ll chk[200010];
ll siz[200010];
map<ll, ll> mp[200010];
map<ll, ll> st[200010];
ll bun[200010];
ll ans[200010];

void dfs0(ll here, ll pa)
{
	siz[here] = 1;
	
	for(auto &i : vec[here])
	{
		dfs0(i, here);
		siz[here] += siz[i];
	}
}

void dfs(ll here, ll pa)
{
	if((ll)vec[here].size() == 0)
	{
		mp[here][siz[here]] = here;
		bun[here] = here;
		return;
	}
	
	for(auto &i : vec[here])
	{
		dfs(i, here);
		
		if(ans[i] == -1)
			ans[here] = -1;
	}
	
	if(ans[here] == -1)
		return;
	
	ll maxx = -1;
	ll w = -1;
	
	for(auto &i : vec[here])
	{
		if(maxx < siz[i])
		{
			maxx = siz[i];
			w = i;
		}
	}
	
	bun[here] = bun[w];
	
	for(auto &i : vec[here])
	{
		if(i == w)
			continue;
		
		for(auto &j : mp[bun[i]])
		{
			if(j.fi == 1)
				continue;
			
			auto p = mp[bun[here]].lower_bound(j.fi);
			
			if(p != mp[bun[here]].end())
			{
				auto gap = (*p);
				ll V = gap.se;
				ll U = j.se;
				
				for(auto &k : st[U])
				{
					if(st[V].find(k.fi) == st[V].end())
					{
						ans[here] = -1;
						return;
					}
					
					if(siz[st[V][k.fi]] < siz[k.se])
					{
						ans[here] = -1;
						return;
					}
				}
				
				if(gap.fi == j.fi)
				{
					for(auto &k : st[V])
					{
						if(st[U].find(k.fi) == st[U].end())
						{
							ans[here] = -1;
							return;
						}
						
						if(siz[st[U][k.fi]] < siz[k.se])
						{
							ans[here] = -1;
							return;
						}
					}
				}
			}
			
			p = mp[bun[here]].upper_bound(j.fi);
			
			if(p != mp[bun[here]].begin())
			{
				p--;
				auto gap = (*p);
				ll V = gap.se;
				ll U = j.se;
				
				for(auto &k : st[V])
				{
					if(st[U].find(k.fi) == st[U].end())
					{
						ans[here] = -1;
						return;
					}
					
					if(siz[st[U][k.fi]] < siz[k.se])
					{
						ans[here] = -1;
						return;
					}
				}
			}
		}
		
		for(auto &j : mp[bun[i]])
			mp[bun[here]][j.fi] = j.se;
	}
	
	auto p = mp[bun[here]].rbegin();
	auto gap = (*p);
	ll V = gap.se;
	ll U = here;
	
	for(auto &k : st[V])
	{
		if(st[U].find(k.fi) == st[U].end())
		{
			ans[here] = -1;
			return;
		}
		
		if(siz[st[U][k.fi]] < siz[k.se])
		{
			ans[here] = -1;
			return;
		}
	}
	
	if(gap.fi == siz[here])
	{
		for(auto &k : st[V])
		{
			if(st[U].find(k.fi) == st[U].end())
			{
				ans[here] = -1;
				return;
			}
			
			if(siz[st[U][k.fi]] < siz[k.se])
			{
				ans[here] = -1;
				return;
			}
		}
	}
	
	mp[bun[here]][siz[here]] = here;
}

vector<ll> beechtree(ll N, ll M, vector<ll> P, vector<ll> C)
{
	for(ll i = 1 ; i < N ; i++)
		zip.push_back(C[i]);
	
	compress(zip);
	
	M = (ll)zip.size();
	
	for(ll i = 1 ; i < N ; i++)
		C[i] = lower_bound(zip.begin(), zip.end(), C[i]) - zip.begin() + 1;
	
	for(ll i = 1 ; i < N ; i++)
		vec[P[i]].push_back(i);
	
	for(ll i = 0 ; i < N ; i++)
	{
		set<ll> st22;
		
		for(auto &j : vec[i])
			st22.insert(C[j]);
		
		if((ll)st22.size() != (ll)vec[i].size())
			ans[i] = -1;
	}
	
	dfs0(0, -1);
	
	for(ll i = 0 ; i < N ; i++)
	{
		for(auto &j : vec[i])
			st[i][C[j]] = j;
	}
	
	dfs(0, -1);
	
	vector<ll> anss;
	
	for(ll i = 0 ; i < N ; i++)
	{
		if(ans[i] == -1)
			anss.push_back(0);
		else
			anss.push_back(1);
	}
	
	return anss;
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 5 / 5
• Subtask 3: 9 / 9
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 12 / 12
• Subtask 8: 17 / 17
• Subtask 9: 12 / 12