oj.uz

Submission #408808

# Submission time Handle Problem Language Result Execution time Memory
408808 2021-05-19T16:37:52 Z Jasiekstrz Regions (IOI09_regions) C++17
75 / 100
 8000 ms 51360 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=300;
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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5576 KB Output is correct
2 Correct 4 ms 5576 KB Output is correct
3 Correct 6 ms 5576 KB Output is correct
4 Correct 7 ms 5576 KB Output is correct
5 Correct 10 ms 5576 KB Output is correct
6 Correct 31 ms 5704 KB Output is correct
7 Correct 47 ms 5648 KB Output is correct
8 Correct 52 ms 5704 KB Output is correct
9 Correct 62 ms 6728 KB Output is correct
10 Correct 110 ms 6304 KB Output is correct
11 Correct 250 ms 6600 KB Output is correct
12 Correct 305 ms 7496 KB Output is correct
13 Correct 278 ms 6648 KB Output is correct
14 Correct 482 ms 7368 KB Output is correct
15 Correct 1103 ms 14788 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2420 ms 12676 KB Output is correct
2 Correct 2316 ms 9800 KB Output is correct
3 Correct 7116 ms 16720 KB Output is correct
4 Correct 516 ms 7872 KB Output is correct
5 Correct 729 ms 12048 KB Output is correct
6 Correct 1034 ms 13884 KB Output is correct
7 Correct 1543 ms 15264 KB Output is correct
8 Correct 3087 ms 32260 KB Output is correct
9 Correct 5709 ms 25208 KB Output is correct
10 Execution timed out 8045 ms 51360 KB Time limit exceeded
11 Execution timed out 8087 ms 36544 KB Time limit exceeded
12 Correct 3284 ms 19088 KB Output is correct
13 Correct 5629 ms 20316 KB Output is correct
14 Correct 5566 ms 23300 KB Output is correct
15 Execution timed out 8013 ms 30112 KB Time limit exceeded
16 Execution timed out 8018 ms 50340 KB Time limit exceeded
17 Execution timed out 8006 ms 49752 KB Time limit exceeded