제출 #408803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
408803		Jasiekstrz	Regions (IOI09_regions)	C++17	75 / 100	8064 ms	51388 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=400;
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];
int pot;
int tree[2*P+10];
void add(int l,int r,int c)
{
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			tree[l++]+=c;
		if(r%2==0)
			tree[r--]+=c;
	}
	return;
}
int read(int x)
{
	int ans=0;
	for(x+=pot-1;x>0;x/=2)
		ans+=tree[x];
	return ans;
}
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;
	for(auto v:reg[a])
		add(bg[v],en[v],1);
	for(auto v:reg[b])
		ans+=read(bg[v]);
	for(auto v:reg[a])
		add(bg[v],en[v],-1);
	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);
		}
	}
	for(pot=1;pot<n;pot*=2);
	int nr=0;
	delete dfs(1,nr,r);
	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: 60 / 85