Submission #408816

#	Time	Username	Problem	Language	Result	Execution time	Memory
408816		Jasiekstrz	Regions (IOI09_regions)	C++17	95 / 100	8023 ms	49324 KiB

regions

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
const int P=3e5;
const int R=25e3;
const int S=500;
vector<int> big;
bool is_big[R+10];
int nrbig[R+10];
int dd[N/S+10][R+10];
int du[N/S+10][R+10];
vector<int> reg[R+10];
vector<int> e[N+10];
int t[N+10];
int bg[N+10];
int en[N+10];
int cur_u[R+10];
vector<pair<int,bool>> ev[R+10];
unordered_map<int,int>* dfs(int x,int &nr,int r)
{
	bg[x]=++nr;
	cur_u[t[x]]++;
	unordered_map<int,int> *mp=new unordered_map<int,int>;
	for(auto v:e[x])
	{
		unordered_map<int,int> *mp2=dfs(v,nr,r);
		if((mp2->size())>(mp->size()))
			swap(mp,mp2);
		for(auto v2:*mp2)
			(*mp)[v2.fi]+=v2.se;
		delete mp2;
	}
	cur_u[t[x]]--;
	en[x]=nr;
	if(is_big[t[x]])
	{
		for(int i=1;i<=r;i++)
			du[nrbig[t[x]]][i]+=cur_u[i];
		for(auto v:*mp)
			dd[nrbig[t[x]]][v.fi]+=v.se;
	}
	(*mp)[t[x]]++;
	return mp;
}
int solve(int a,int b)
{
	int ans=0;
	int cur=0;
	for(size_t i=0,j=0;i<ev[a].size() && j<ev[b].size();)
	{
		pair<int,bool> x;
		if(ev[a][i]<ev[b][j])
		{
			x=ev[a][i];
			i++;
			if(x.se)
				cur++;
			else
				cur--;
		}
		else
		{
			x=ev[b][j];
			j++;
			if(x.se)
				ans+=cur;
		}

	}
	return ans;
}
int main()
{
	int n,r,q;
	cin>>n>>r>>q;
	cin>>t[1];
	reg[t[1]].push_back(1);
	for(int i=2;i<=n;i++)
	{
		int a;
		cin>>a>>t[i];
		e[a].push_back(i);
		reg[t[i]].push_back(i);
	}
	for(int i=1;i<=r;i++)
	{
		if(reg[i].size()>=S)
		{
			is_big[i]=true;
			nrbig[i]=big.size();
			big.push_back(i);
		}
	}
	int nr=0;
	delete dfs(1,nr,r);
	for(int i=1;i<=r;i++)
	{
		for(auto v:reg[i])
		{
			ev[i].emplace_back(bg[v],true);
			ev[i].emplace_back(en[v]+1,false);
		}
		sort(ev[i].begin(),ev[i].end());
	}
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		if(is_big[a])
			cout<<dd[nrbig[a]][b]<<endl;
		else if(is_big[b])
			cout<<du[nrbig[b]][a]<<endl;
		else
			cout<<solve(a,b)<<endl;
	}
	return 0;
}

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