oj.uz

Submission #116566

# Submission time Handle Problem Language Result Execution time Memory
116566 2019-06-13T00:18:06 Z kig9981 Regions (IOI09_regions) C++17
0 / 100
 45 ms 14200 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6 ms 5504 KB Time limit exceeded (wall clock)
2 Execution timed out 7 ms 5632 KB Time limit exceeded (wall clock)
3 Execution timed out 6 ms 5632 KB Time limit exceeded (wall clock)
4 Execution timed out 6 ms 5632 KB Time limit exceeded (wall clock)
5 Execution timed out 6 ms 5632 KB Time limit exceeded (wall clock)
6 Execution timed out 6 ms 5504 KB Time limit exceeded (wall clock)
7 Execution timed out 6 ms 5632 KB Time limit exceeded (wall clock)
8 Execution timed out 6 ms 5504 KB Time limit exceeded (wall clock)
9 Execution timed out 7 ms 5632 KB Time limit exceeded (wall clock)
10 Execution timed out 6 ms 5632 KB Time limit exceeded (wall clock)
11 Execution timed out 5 ms 5632 KB Time limit exceeded (wall clock)
12 Execution timed out 6 ms 5760 KB Time limit exceeded (wall clock)
13 Execution timed out 6 ms 5788 KB Time limit exceeded (wall clock)
14 Execution timed out 6 ms 5808 KB Time limit exceeded (wall clock)
15 Execution timed out 7 ms 5936 KB Time limit exceeded (wall clock)

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7 ms 6204 KB Time limit exceeded (wall clock)
2 Execution timed out 7 ms 6264 KB Time limit exceeded (wall clock)
3 Execution timed out 8 ms 6320 KB Time limit exceeded (wall clock)
4 Execution timed out 7 ms 5860 KB Time limit exceeded (wall clock)
5 Execution timed out 6 ms 5888 KB Time limit exceeded (wall clock)
6 Execution timed out 8 ms 6144 KB Time limit exceeded (wall clock)
7 Execution timed out 8 ms 6400 KB Time limit exceeded (wall clock)
8 Execution timed out 19 ms 10756 KB Time limit exceeded (wall clock)
9 Execution timed out 24 ms 10360 KB Time limit exceeded (wall clock)
10 Execution timed out 21 ms 10616 KB Time limit exceeded (wall clock)
11 Execution timed out 36 ms 11816 KB Time limit exceeded (wall clock)
12 Execution timed out 41 ms 14072 KB Time limit exceeded (wall clock)
13 Execution timed out 36 ms 13464 KB Time limit exceeded (wall clock)
14 Execution timed out 38 ms 13308 KB Time limit exceeded (wall clock)
15 Execution timed out 45 ms 14200 KB Time limit exceeded (wall clock)
16 Execution timed out 38 ms 14200 KB Time limit exceeded (wall clock)
17 Execution timed out 34 ms 14200 KB Time limit exceeded (wall clock)