oj.uz

Submission #408816

# Submission time Handle Problem Language Result Execution time Memory
408816 2021-05-19T17:06:11 Z Jasiekstrz Regions (IOI09_regions) C++17
95 / 100
 8000 ms 49324 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=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.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 5 ms 6088 KB Output is correct
4 Correct 6 ms 6088 KB Output is correct
5 Correct 14 ms 6216 KB Output is correct
6 Correct 36 ms 6344 KB Output is correct
7 Correct 44 ms 6216 KB Output is correct
8 Correct 51 ms 6344 KB Output is correct
9 Correct 73 ms 7284 KB Output is correct
10 Correct 105 ms 6856 KB Output is correct
11 Correct 81 ms 7268 KB Output is correct
12 Correct 94 ms 8136 KB Output is correct
13 Correct 204 ms 7616 KB Output is correct
14 Correct 213 ms 8420 KB Output is correct
15 Correct 239 ms 15000 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1290 ms 13052 KB Output is correct
2 Correct 1102 ms 11072 KB Output is correct
3 Correct 2128 ms 16576 KB Output is correct
4 Correct 299 ms 8372 KB Output is correct
5 Correct 409 ms 12332 KB Output is correct
6 Correct 879 ms 11392 KB Output is correct
7 Correct 1312 ms 11460 KB Output is correct
8 Correct 1093 ms 23532 KB Output is correct
9 Correct 2220 ms 19532 KB Output is correct
10 Correct 3232 ms 30912 KB Output is correct
11 Correct 3222 ms 18556 KB Output is correct
12 Correct 1981 ms 19960 KB Output is correct
13 Correct 2416 ms 21060 KB Output is correct
14 Correct 3638 ms 24132 KB Output is correct
15 Correct 5651 ms 29300 KB Output is correct
16 Correct 6928 ms 49324 KB Output is correct
17 Execution timed out 8023 ms 48780 KB Time limit exceeded