oj.uz

Submission #408803

# Submission time Handle Problem Language Result Execution time Memory
408803 2021-05-19T16:30:26 Z Jasiekstrz Regions (IOI09_regions) C++17
75 / 100
 8000 ms 51388 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];
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 10 ms 5576 KB Output is correct
5 Correct 14 ms 5576 KB Output is correct
6 Correct 23 ms 5704 KB Output is correct
7 Correct 48 ms 5704 KB Output is correct
8 Correct 42 ms 5832 KB Output is correct
9 Correct 48 ms 6760 KB Output is correct
10 Correct 133 ms 6236 KB Output is correct
11 Correct 225 ms 6616 KB Output is correct
12 Correct 280 ms 7496 KB Output is correct
13 Correct 256 ms 6608 KB Output is correct
14 Correct 490 ms 7356 KB Output is correct
15 Correct 1054 ms 14784 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 2526 ms 12528 KB Output is correct
2 Correct 2239 ms 9732 KB Output is correct
3 Correct 6844 ms 16792 KB Output is correct
4 Correct 533 ms 7864 KB Output is correct
5 Correct 802 ms 12084 KB Output is correct
6 Correct 1143 ms 13904 KB Output is correct
7 Correct 2616 ms 13228 KB Output is correct
8 Correct 3336 ms 32256 KB Output is correct
9 Correct 7264 ms 18320 KB Output is correct
10 Execution timed out 8058 ms 51388 KB Time limit exceeded
11 Execution timed out 8054 ms 17192 KB Time limit exceeded
12 Correct 3569 ms 18912 KB Output is correct
13 Correct 5620 ms 20212 KB Output is correct
14 Correct 5664 ms 23288 KB Output is correct
15 Execution timed out 8020 ms 30084 KB Time limit exceeded
16 Execution timed out 8064 ms 50336 KB Time limit exceeded
17 Execution timed out 8032 ms 49748 KB Time limit exceeded