Submission #116566

#	Time	Username	Problem	Language	Result	Execution time	Memory
116566		kig9981	Regions (IOI09_regions)	C++17	0 / 100	45 ms	14200 KiB

regions

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
 
using namespace std;
 
const int rt=448, MAX_SIZE=1<<20;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[200000], sum2[200000], tree[200001];
long long ans[200000/rt+1][25000], ans2[200000/rt+1][25000];
char buf[MAX_SIZE];

inline char get_char()
{
	static int p=0, s=0;
	if(p==s) {
		p=0;
		s=fread(buf,1,MAX_SIZE,stdin);
        if(p==s) return 0;
	}
	return buf[p++];
}

inline int get_int()
{
	int ret=0;
	bool is_negative=false;
	char c=-1;
	while(!('0'<=c && c<='9') && c!='-') c=get_char();
	if(c=='-') {
		is_negative=true;
		c=get_char();
	}
	while('0'<=c && c<='9') ret*=10, ret+=c-'0', c=get_char();
	return (is_negative ? -ret:ret);
}
 
void add_tree(int n, int v)
{
	for(++n;n<=200000;n+=n&-n) tree[n]+=v;
}
 
int get_sum(int n)
{
	int ret=0;
	for(++n;n;n-=n&-n) ret+=tree[n];
	return ret;
}
 
int get_sum(int s, int e)
{
	return get_sum(e)-get_sum(s-1);
}
 
void dfs(int c)
{
	num[c]=++node_cnt;
	for(auto n: adj[c]) dfs(n);
	fin[c]=node_cnt;
}
 
void dfs2(int c, int v)
{
	sum[c]+=RV[c]==v;
	sum2[c]=RV[c]==v;
	for(auto n: adj[c]) {
		sum[n]=sum[c];
		dfs2(n,v);
		sum2[c]+=sum2[n];
	}
}
 
int main()
{
	int N=get_int(), M=get_int(), Q=get_int(), p;
	R[RV[0]=get_int()-1].push_back(0);
	for(int i=1;i<N;i++) {
		adj[get_int()-1].push_back(i);
		R[RV[i]=get_int()-1].push_back(i);
	}
	dfs(0);
	for(int i=0;i<M;i++) if(R[i].size()>=rt) {
		sum[0]=0;
		dfs2(0,i);
		for(int j=0;j<N;j++) {
			ans[O.size()][RV[j]]+=sum[j];
			ans2[O.size()][RV[j]]+=sum2[j];
		}
		O.push_back(i);
	}
	while(Q--) {
		int a=get_int()-1, b=get_int()-1;
		if(R[a].size()>=rt) printf("%lld\n",ans[lower_bound(O.begin(),O.end(),a)-O.begin()][b]);
		else if(R[b].size()>=rt) printf("%lld\n",ans2[lower_bound(O.begin(),O.end(),b)-O.begin()][a]);
		else {
			long long ans=0;
			for(auto r: R[b]) add_tree(num[r],1);
			for(auto r: R[a]) ans+=get_sum(num[r],fin[r]);
			for(auto r: R[b]) add_tree(num[r],-1);
			printf("%lld\n",ans);
		}
		fflush(stdout);
	}
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:76:45: warning: unused variable 'p' [-Wunused-variable]
  int N=get_int(), M=get_int(), Q=get_int(), p;
                                             ^

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