oj.uz

Submission #408799

# Submission time Handle Problem Language Result Execution time Memory
408799 2021-05-19T16:23:15 Z Jasiekstrz Regions (IOI09_regions) C++17
75 / 100
 8000 ms 54860 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];
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;
}
map<int,int>* dfs(int x,int &nr,int r)
{
	bg[x]=++nr;
	cur_u[t[x]]++;
	map<int,int> *mp=new map<int,int>;
	for(auto v:e[x])
	{
		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 5704 KB Output is correct
5 Correct 14 ms 5576 KB Output is correct
6 Correct 23 ms 5828 KB Output is correct
7 Correct 48 ms 5704 KB Output is correct
8 Correct 44 ms 5704 KB Output is correct
9 Correct 76 ms 6856 KB Output is correct
10 Correct 110 ms 6200 KB Output is correct
11 Correct 227 ms 6728 KB Output is correct
12 Correct 255 ms 7688 KB Output is correct
13 Correct 241 ms 6604 KB Output is correct
14 Correct 488 ms 7456 KB Output is correct
15 Correct 1085 ms 15936 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2733 ms 13052 KB Output is correct
2 Correct 2443 ms 9880 KB Output is correct
3 Correct 7457 ms 17920 KB Output is correct
4 Correct 491 ms 7868 KB Output is correct
5 Correct 635 ms 12928 KB Output is correct
6 Correct 2216 ms 11404 KB Output is correct
7 Correct 4164 ms 11224 KB Output is correct
8 Correct 6250 ms 25920 KB Output is correct
9 Correct 7362 ms 18976 KB Output is correct
10 Execution timed out 8052 ms 34664 KB Time limit exceeded
11 Execution timed out 8068 ms 17340 KB Time limit exceeded
12 Correct 3270 ms 19240 KB Output is correct
13 Correct 5361 ms 21008 KB Output is correct
14 Correct 5525 ms 23752 KB Output is correct
15 Execution timed out 8079 ms 32268 KB Time limit exceeded
16 Execution timed out 8021 ms 54860 KB Time limit exceeded
17 Execution timed out 8010 ms 53576 KB Time limit exceeded