Submission #249429

#	Time	Username	Problem	Language	Result	Execution time	Memory
249429		MohamedAhmed04	Regions (IOI09_regions)	C++14	50 / 100	3158 ms	131072 KiB

regions

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;
const int MAXSZ = 450 ;
const int MAXR = 25005 ;

int arr[MAX] , in[MAX] , out[MAX] ;
int Reg[MAX] , ans1[MAXSZ][MAXR] , ans2[MAXR][MAXSZ] ;
vector<int>nodes ;
int n , r , q ;

vector< vector<int> >adj(MAX) ;
vector< vector< pair<int , int> > >RegNodes(MAX) ;

int tim = 0 ;

void dfs(int node)
{
	nodes.push_back(node) ;
	in[node] = ++tim ;
	for(auto &child : adj[node])
		dfs(child) ;
	out[node] = tim ;
}

int now ;

int dfs2(int node , int cnt)
{
	int x = 0 ;
	for(auto &child : adj[node])
		x += dfs2(child , cnt + (arr[node] == now)) ;
	ans1[now][arr[node]] += cnt ;
	ans2[arr[node]][now] += x ;
	return (x + (arr[node] == now)) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>r>>q ;
	cin>>arr[1] ;
	for(int i = 2 ; i <= n ; ++i)
	{
		int x ;
		cin>>x>>arr[i] ;
		adj[x].push_back(i) ;
	}
	dfs(1) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		Reg[arr[i]]++ ;
		RegNodes[arr[i]].emplace_back(in[i] , i) ;
	}
	int SZ = ceil(sqrt(n)) ;
	for(int i = 1 ; i <= r ; ++i)
	{
		sort(RegNodes[i].begin() , RegNodes[i].end()) ;
		if(Reg[i] >= SZ)
			now = i , dfs2(1 , 0) ;
	}
	stack<int>s ;
	while(q--)
	{
		int a , b ;
		cin>>a>>b ;
		if(Reg[a] >= SZ)
			cout<<ans1[a][b]<<endl ;
		else if(Reg[b] >= SZ)
			cout<<ans2[a][b]<<endl ;
		else
		{
			while(s.size() > 0)
				s.pop() ;
			int idx1 = 0 , idx2 = 0 , cnt = 0 ;
			for(int i = 0 ; i < Reg[a] + Reg[b] ; ++i)
			{
				int x = 1e9 , y = 1e9 ;
				if(idx1 != Reg[a])
					x = RegNodes[a][idx1].first ;
				if(idx2 != Reg[b])
					y = RegNodes[b][idx2].first ;
				while(s.size() > 0 && s.top() < min(x , y))
					s.pop() ;
				if(x < y)
					s.push(out[RegNodes[a][idx1].second]) , idx1++ ;
				else
					cnt += s.size() , idx2++ ;
			}
			cout<<cnt<<endl ;
		}
	}
	return 0 ;
}		

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