Submission #116568

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116568	2019-06-13T00:20:47 Z	kig9981	Regions (IOI09_regions)	C++17	95 / 100	8000 ms	41488 KB

regions

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

#include <bits/stdc++.h>
 
using namespace std;
 
const int rt=448;
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];

inline int get_int()
{
	int ret=0;
	bool is_negative=false;
	char c=-1;
	while(!('0'<=c && c<='9') && c!='-') c=getchar_unlocked();
	if(c=='-') {
		is_negative=true;
		c=getchar_unlocked();
	}
	while('0'<=c && c<='9') ret*=10, ret+=c-'0', c=getchar_unlocked();
	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();
	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;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5632 KB	Output is correct
2	Correct	7 ms	5632 KB	Output is correct
3	Correct	8 ms	5632 KB	Output is correct
4	Correct	20 ms	5632 KB	Output is correct
5	Correct	10 ms	5680 KB	Output is correct
6	Correct	19 ms	5632 KB	Output is correct
7	Correct	20 ms	5632 KB	Output is correct
8	Correct	31 ms	5760 KB	Output is correct
9	Correct	43 ms	6016 KB	Output is correct
10	Correct	58 ms	6144 KB	Output is correct
11	Correct	127 ms	6504 KB	Output is correct
12	Correct	148 ms	6784 KB	Output is correct
13	Correct	243 ms	6528 KB	Output is correct
14	Correct	383 ms	7168 KB	Output is correct
15	Correct	382 ms	8704 KB	Output is correct

Subtask #2

80.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1890 ms	10616 KB	Output is correct
2	Correct	2071 ms	9720 KB	Output is correct
3	Correct	3404 ms	12024 KB	Output is correct
4	Correct	430 ms	7040 KB	Output is correct
5	Correct	463 ms	8236 KB	Output is correct
6	Correct	646 ms	15736 KB	Output is correct
7	Correct	2237 ms	12384 KB	Output is correct
8	Correct	1346 ms	30172 KB	Output is correct
9	Correct	4617 ms	13944 KB	Output is correct
10	Correct	5008 ms	41488 KB	Output is correct
11	Execution timed out	8007 ms	13944 KB	Time limit exceeded
12	Correct	2095 ms	17740 KB	Output is correct
13	Correct	3129 ms	17528 KB	Output is correct
14	Correct	3334 ms	24160 KB	Output is correct
15	Correct	5401 ms	20836 KB	Output is correct
16	Correct	5754 ms	24056 KB	Output is correct
17	Correct	4624 ms	29884 KB	Output is correct