oj.uz

Submission #408805

# Submission time Handle Problem Language Result Execution time Memory
408805 2021-05-19T16:34:24 Z Jasiekstrz Regions (IOI09_regions) C++17
75 / 100
 8000 ms 131076 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=200;
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 5 ms 5576 KB Output is correct
4 Correct 9 ms 5576 KB Output is correct
5 Correct 12 ms 5576 KB Output is correct
6 Correct 26 ms 5704 KB Output is correct
7 Correct 47 ms 5704 KB Output is correct
8 Correct 40 ms 5704 KB Output is correct
9 Correct 93 ms 6760 KB Output is correct
10 Correct 139 ms 6216 KB Output is correct
11 Correct 213 ms 6632 KB Output is correct
12 Correct 246 ms 7732 KB Output is correct
13 Correct 290 ms 6616 KB Output is correct
14 Correct 500 ms 7396 KB Output is correct
15 Correct 1063 ms 14716 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1336 ms 13356 KB Output is correct
2 Correct 1252 ms 11352 KB Output is correct
3 Correct 1498 ms 18608 KB Output is correct
4 Correct 604 ms 7760 KB Output is correct
5 Correct 845 ms 12148 KB Output is correct
6 Correct 886 ms 13696 KB Output is correct
7 Correct 1688 ms 16068 KB Output is correct
8 Correct 3218 ms 32260 KB Output is correct
9 Correct 4339 ms 31232 KB Output is correct
10 Execution timed out 8102 ms 103612 KB Time limit exceeded
11 Runtime error 1203 ms 131076 KB Execution killed with signal 9
12 Correct 3652 ms 59668 KB Output is correct
13 Correct 5011 ms 62080 KB Output is correct
14 Correct 5385 ms 25004 KB Output is correct
15 Execution timed out 8066 ms 30156 KB Time limit exceeded
16 Runtime error 249 ms 131076 KB Execution killed with signal 9
17 Execution timed out 8010 ms 51400 KB Time limit exceeded