Submission #116569

# Submission time Handle Problem Language Result Execution time Memory
116569 2019-06-13T00:22:54 Z kig9981 Regions (IOI09_regions) C++17
0 / 100
7 ms 5680 KB
#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[rt][25000], ans2[rt][25000];

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

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:66:35: warning: array subscript is below array bounds [-Warray-bounds]
  for(int i=0;i<M;i++) if(R[i].size()>=rt) {
                          ~~~~~~~~~^~
# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5632 KB Unexpected end of file - int32 expected
2 Incorrect 6 ms 5632 KB Unexpected end of file - int32 expected
3 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
4 Incorrect 6 ms 5632 KB Unexpected end of file - int32 expected
5 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
6 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
7 Incorrect 6 ms 5632 KB Unexpected end of file - int32 expected
8 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
9 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
10 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
11 Incorrect 6 ms 5552 KB Unexpected end of file - int32 expected
12 Incorrect 6 ms 5632 KB Unexpected end of file - int32 expected
13 Incorrect 6 ms 5624 KB Unexpected end of file - int32 expected
14 Incorrect 6 ms 5632 KB Unexpected end of file - int32 expected
15 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5632 KB Unexpected end of file - int32 expected
2 Incorrect 6 ms 5632 KB Unexpected end of file - int32 expected
3 Incorrect 6 ms 5680 KB Unexpected end of file - int32 expected
4 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
5 Incorrect 7 ms 5632 KB Unexpected end of file - int32 expected
6 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
7 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
8 Incorrect 6 ms 5652 KB Unexpected end of file - int32 expected
9 Incorrect 6 ms 5632 KB Unexpected end of file - int32 expected
10 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
11 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
12 Incorrect 6 ms 5632 KB Unexpected end of file - int32 expected
13 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
14 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
15 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
16 Incorrect 6 ms 5504 KB Unexpected end of file - int32 expected
17 Incorrect 7 ms 5504 KB Unexpected end of file - int32 expected