Submission #1266381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266381		namhh	Regions (IOI09_regions)	C++20	100 / 100	3571 ms	41008 KiB

regions

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
const int bl = 450;
int n,r,q,ans[bl+5][25005],st[N],ed[N],h[N],cnt[N],check[N],val[N],timer = 1;
vector<int>adj[N],reg[N],reg1[N],heavy;
void dfs(int u, int p){
	st[u] = timer;
	reg[h[u]].push_back(st[u]);
	timer++;
	for(int v: adj[u]){
		if(v != p) dfs(v,u);
	}
	ed[u] = timer-1;
}
void dfs1(int u, int p){
	for(int i = 0; i < heavy.size(); i++){
		if(h[u] == heavy[i]) continue;
		ans[i][h[u]] += cnt[heavy[i]];
	}
	cnt[h[u]]++;
	for(int v: adj[u]){
		if(v != p) dfs1(v,u);
	}
	cnt[h[u]]--;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> r >> q >> h[1];
	reg1[h[1]].push_back(1);
	for(int i = 2; i <= n; i++){
		int p;
		cin >> p >> h[i];
		adj[p].push_back(i);
		adj[i].push_back(p);
		reg1[h[i]].push_back(i);
	}
	dfs(1,0);
	int dem = 0;
	for(int i = 1; i <= r; i++){
		sort(reg[i].begin(),reg[i].end());
		if(reg[i].size() > bl){
			check[i] = 1;
			val[i] = dem;
			dem++;
			heavy.push_back(i);
		}
	}
	dfs1(1,0);
	while(q--){
		int l,r;
		cin >> l >> r;
		if(check[l] == 1) cout << ans[val[l]][r] << endl;
		else{
			long long res = 0;
			for(int v: reg1[l]){
				int x = st[v];
				int y = ed[v];
				int val1 = upper_bound(reg[r].begin(),reg[r].end(),y)-reg[r].begin();
				int val2 = lower_bound(reg[r].begin(),reg[r].end(),x)-reg[r].begin();
				res += val1-val2;
			}
			cout << res << endl;
		}
	}
}
//-----+--+----+-==-=*==--=+----------==----------------+=-----==-=+-==----------------
//---===+=----+=----=*=+=*+----------==-----------+=-----==-----==--+-+----------------
//---+=**=-=+---------***+----=------=-------------=-------+-----==-+--=---------------
//----*+-+++**++------=#+----===-----=-------------=-------==-----+-=+=-+--------------
//----++#***+*+++-----=+-----=-=----+---------------+-------+=-----*=-==-+-------------
//---+=+**++**++++==++*=-----===----+---------------+----=---=-----=*+*=-==------------
//---++**==+--++++++***-----+-+-----+---------------==---==--==-----+**---+------------
//----++*#=-+++***+***------+-+-----+----------------=----+---*+=---=*#=-=-+-----------
//-----=**+++*+++**%++-----=--+-----+----------------=----*=--==+==++***-=+==----------
//-------**#**++*%%@==-----=--+-----+-------------=+++++=-+=---+=+=-=+**--+++----------
//---------====+@@%@-=-----+--+--=+++++--------------=----+==--===---+*---+==+---------
//-----------=@*%%%%-=-----+=-==-----=---------------=----+--=-==+-=-=*----++==--------
//----------%#=%=#%%==-----=+--=-----=---------------+----+--===*=*==**=---+-++--------
//--------+@++@=*@%*-=-----=+=-=-----==-------------++-*%%%***=++-+=-+-+---=-===-------
//-------#%-=%=+@%@+-=-----=+=--+++*==*=------------**@*##%*--=-+-----=+---==-+==------
//------=%+-=%=%*@@--=-----=*#*=+*###@%*---------=+*++%***##=-+-+------+---==-=+=------
//-------%*-=%@+@@+-*=-----+-=--@##*##=+==----------=-#*#***-==-+------+---==--++------
//-------+@=+@@*@*-=-=-----=-==-*#%*##=----------------++=+=----+------+---==--==+-----
//--------%@@%%@*=--+=-----=---+=+#==*-------------------==-----+------+---==---=+-----
//----------%+=#-=--==-----+-------===--------------------------*------+---==---+==----
//---------##-%+-=---=-----++----------------------------------=*------=---==---=+=----
//--------=#-*@=-=---=-----**=----------------=----------------+*------=---==----++----
//-------=@==%*-==---=-----++*---------------------------------*+------+---==----++=---
//------=%*-=@--==---=-----+++*-------------------------------**=------+---==----==+---
//------*#--##--==---=-----+++*+--------------------+--------+**=------+---=-----==+---
//-----=@=--@*---=---=-----+++#+*=--------=+=----=+=-------=#+**-------+---+-----==+---
//----=%+--=@+---=---=-----=+**++**=---------------------=*+****------==---+-----===---
//----*#---*@=---=--==-----=*+#++*+++*=---------------=*#*++#+*+==----+==-+=-----====--
//---=@=---%%----=--=+-----=*+#++*++++***+----------*****+++#**++-----+==-+-------===--
//---%#----%%---==--=+------*+*++*++**+***+**++=+****+==++*+**#-+-----+==-+-------+==--
//--=@=---=%#---==--+*------*++*+*++#+*****++++****+--==*=*****==----===-==-------+==--
//--##----=@*---+=--+*------=++*+*++*++++++*******=-------+***==-----===-==-------+==--
//-=@+----+@=---+=--+#=-----=*+*+*++#++*+++**#*++-+-------+***-+-----+===+--------*==--
//-*@=----*@=---=---+*+------++*+*+*-=++*+***=-+--+--------#**-=-----*====--------*==--
//=%%-----#@---==---=**------++****---------*=----+--------=#=+-----=*==*---------*==--
//=@*-----%@---==---=*#------++*+------=+%@##@+==%%+*+==----+==-----+*+-++++=+++*++==--

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85