oj.uz

Submission #408817

# Submission time Handle Problem Language Result Execution time Memory
408817 2021-05-19T17:08:17 Z Jasiekstrz Regions (IOI09_regions) C++17
100 / 100
 7869 ms 50772 KB 
#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];
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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6088 KB Output is correct
2 Correct 4 ms 6088 KB Output is correct
3 Correct 6 ms 6092 KB Output is correct
4 Correct 10 ms 6088 KB Output is correct
5 Correct 13 ms 6216 KB Output is correct
6 Correct 25 ms 6344 KB Output is correct
7 Correct 31 ms 6216 KB Output is correct
8 Correct 54 ms 6372 KB Output is correct
9 Correct 55 ms 7368 KB Output is correct
10 Correct 83 ms 6832 KB Output is correct
11 Correct 150 ms 7240 KB Output is correct
12 Correct 191 ms 8020 KB Output is correct
13 Correct 165 ms 7512 KB Output is correct
14 Correct 262 ms 8404 KB Output is correct
15 Correct 249 ms 15012 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1224 ms 13160 KB Output is correct
2 Correct 1126 ms 11072 KB Output is correct
3 Correct 2109 ms 16780 KB Output is correct
4 Correct 365 ms 8476 KB Output is correct
5 Correct 451 ms 12360 KB Output is correct
6 Correct 1167 ms 13944 KB Output is correct
7 Correct 1226 ms 13828 KB Output is correct
8 Correct 2416 ms 32172 KB Output is correct
9 Correct 1939 ms 19380 KB Output is correct
10 Correct 5612 ms 50772 KB Output is correct
11 Correct 3503 ms 18568 KB Output is correct
12 Correct 1896 ms 19916 KB Output is correct
13 Correct 2466 ms 21156 KB Output is correct
14 Correct 3708 ms 24196 KB Output is correct
15 Correct 5930 ms 29308 KB Output is correct
16 Correct 6363 ms 49364 KB Output is correct
17 Correct 7869 ms 48780 KB Output is correct