oj.uz

Submission #116564

# Submission time Handle Problem Language Result Execution time Memory
116564 2019-06-13T00:10:43 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 33048 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=500;
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 6 ms 5680 KB Output is correct
4 Correct 13 ms 5760 KB Output is correct
5 Correct 15 ms 5760 KB Output is correct
6 Correct 16 ms 5632 KB Output is correct
7 Correct 35 ms 5760 KB Output is correct
8 Correct 21 ms 5872 KB Output is correct
9 Correct 45 ms 6196 KB Output is correct
10 Correct 118 ms 6272 KB Output is correct
11 Correct 190 ms 6400 KB Output is correct
12 Correct 177 ms 6784 KB Output is correct
13 Correct 210 ms 6528 KB Output is correct
14 Correct 386 ms 7080 KB Output is correct
15 Correct 403 ms 8964 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1469 ms 10792 KB Output is correct
2 Correct 1904 ms 9676 KB Output is correct
3 Correct 3993 ms 12664 KB Output is correct
4 Correct 452 ms 7100 KB Output is correct
5 Correct 463 ms 8440 KB Output is correct
6 Correct 1457 ms 11056 KB Output is correct
7 Correct 2912 ms 9368 KB Output is correct
8 Correct 2572 ms 15552 KB Output is correct
9 Correct 4698 ms 14204 KB Output is correct
10 Correct 7860 ms 17752 KB Output is correct
11 Execution timed out 8020 ms 14016 KB Time limit exceeded
12 Correct 2325 ms 17732 KB Output is correct
13 Correct 3045 ms 18004 KB Output is correct
14 Correct 3855 ms 24252 KB Output is correct
15 Correct 5471 ms 22184 KB Output is correct
16 Correct 6147 ms 27696 KB Output is correct
17 Correct 5115 ms 33048 KB Output is correct