Submission #661136

#	Time	Username	Problem	Language	Result	Execution time	Memory
661136		parsadox2	Regions (IOI09_regions)	C++14	100 / 100	5341 ms	80244 KiB

regions

#include <bits/stdc++.h>
#define pb push_back
#define debug(x)  cout << #x << " = " << x << ", "
using namespace std;

const int maxn = 2e5 + 10 , maxsq = 500 , maxr = 25e3 + 10;

int n , r , q , col[maxn] , ps[maxn] , tim , cnt[maxn] , ans[maxsq + 10][maxr] , st[maxn] , fn[maxn];
vector <int> g[maxn] , all[maxr] , allst[maxr];

void dfs(int v , int p = -1)
{
	st[v] = tim;
	allst[col[v]].pb(tim);
	tim++;
	if(ps[col[v]] != -1)
		cnt[ps[col[v]]]++;
	for(auto u : g[v])   if(u != p)
	{
		for(int i = 0 ; i < maxsq + 10 ; i++)
			ans[i][col[u]] += cnt[i];
		dfs(u , v);
	}
	if(ps[col[v]] != -1)
		cnt[ps[col[v]]]--;
	fn[v] = tim;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> r >> q;
	cin >> col[0];
	all[col[0]].pb(0);
	memset(ps , -1 , sizeof ps);
	for(int i =  1 ; i < n ; i++)
	{
		int p;
		cin >> p >> col[i];   p--;
		g[p].pb(i);
		all[col[i]].pb(i);
	}
	for(int i = 1 ; i <= r ; i++)   if(all[i].size() > maxsq)
	{
		ps[i] = tim;
		tim++;
	}
	tim = 0;
	dfs(tim);
	while(q--)
	{
		int a , b;
		cin >> a >> b;
		if(ps[a] != -1)
		{
			cout << ans[ps[a]][b] << endl;
			continue;
		}
		int res = 0;
		for(auto u : all[a])
		{
			int l , r;
			int low = -1 , high = allst[b].size();
			while(high - low > 1)
			{
				int mid = (high + low) / 2;
				if(allst[b][mid] >= st[u])
					high = mid;
				else
					low = mid;
			}
			l = high;
			low = -1;  high = allst[b].size();
			while(high - low > 1)
			{
				int mid = (high + low) / 2;
				if(allst[b][mid] < fn[u])
					low = mid;
				else
					high = mid;
			}
			r= high;
			res += (r - l);
		}
		cout << res << endl;
	}
	return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85