oj.uz

Submission #116563

# Submission time Handle Problem Language Result Execution time Memory
116563 2019-06-13T00:09:21 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 59764 KB 
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;
 
const int rt=400;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[200000], sum2[200000], tree[200001];
pair<long long,long long> ans[200000/rt+1][25000];
 
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()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, M, Q, p;
	cin>>N>>M>>Q>>RV[0];
	R[--RV[0]].push_back(0);
	for(int i=1;i<N;i++) {
		cin>>p>>RV[i];
		adj[--p].push_back(i);
		R[--RV[i]].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]].first+=sum[j];
			ans[O.size()][RV[j]].second+=sum2[j];
		}
		O.push_back(i);
	}
	while(Q--) {
		int a, b;
		cin>>a>>b; --a; --b;
		if(R[a].size()>=rt) cout<<ans[lower_bound(O.begin(),O.end(),a)-O.begin()][b].first<<'\n';
		else if(R[b].size()>=rt) cout<<ans[lower_bound(O.begin(),O.end(),b)-O.begin()][a].second<<'\n';
		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);
			cout<<ans<<'\n';
		}
		cout.flush();
	}
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5632 KB Output is correct
2 Correct 6 ms 5632 KB Output is correct
3 Correct 9 ms 5760 KB Output is correct
4 Correct 7 ms 5632 KB Output is correct
5 Correct 13 ms 5680 KB Output is correct
6 Correct 23 ms 5632 KB Output is correct
7 Correct 24 ms 5632 KB Output is correct
8 Correct 23 ms 5872 KB Output is correct
9 Correct 28 ms 6016 KB Output is correct
10 Correct 96 ms 6144 KB Output is correct
11 Correct 96 ms 6408 KB Output is correct
12 Correct 94 ms 6856 KB Output is correct
13 Correct 178 ms 6528 KB Output is correct
14 Correct 301 ms 7040 KB Output is correct
15 Correct 465 ms 9100 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1679 ms 10836 KB Output is correct
2 Correct 1936 ms 9636 KB Output is correct
3 Correct 4075 ms 12764 KB Output is correct
4 Correct 450 ms 7064 KB Output is correct
5 Correct 420 ms 8360 KB Output is correct
6 Correct 624 ms 15600 KB Output is correct
7 Correct 1566 ms 14120 KB Output is correct
8 Correct 1224 ms 31288 KB Output is correct
9 Correct 5124 ms 14120 KB Output is correct
10 Correct 4062 ms 59764 KB Output is correct
11 Execution timed out 8038 ms 14048 KB Time limit exceeded
12 Correct 2185 ms 17784 KB Output is correct
13 Correct 3267 ms 18084 KB Output is correct
14 Correct 4041 ms 24184 KB Output is correct
15 Correct 5641 ms 22180 KB Output is correct
16 Correct 5737 ms 27704 KB Output is correct
17 Correct 5073 ms 32932 KB Output is correct