oj.uz

Submission #116562

# Submission time Handle Problem Language Result Execution time Memory
116562 2019-06-13T00:08:16 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 59836 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=300;
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 7 ms 5680 KB Output is correct
2 Correct 6 ms 5632 KB Output is correct
3 Correct 9 ms 5760 KB Output is correct
4 Correct 10 ms 5632 KB Output is correct
5 Correct 9 ms 5632 KB Output is correct
6 Correct 18 ms 5760 KB Output is correct
7 Correct 32 ms 5760 KB Output is correct
8 Correct 21 ms 5888 KB Output is correct
9 Correct 53 ms 6188 KB Output is correct
10 Correct 68 ms 6144 KB Output is correct
11 Correct 120 ms 6436 KB Output is correct
12 Correct 120 ms 6784 KB Output is correct
13 Correct 206 ms 6684 KB Output is correct
14 Correct 407 ms 7128 KB Output is correct
15 Correct 472 ms 9028 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1642 ms 10876 KB Output is correct
2 Correct 1944 ms 9712 KB Output is correct
3 Correct 3572 ms 12664 KB Output is correct
4 Correct 394 ms 7080 KB Output is correct
5 Correct 430 ms 8568 KB Output is correct
6 Correct 693 ms 15680 KB Output is correct
7 Correct 996 ms 17820 KB Output is correct
8 Correct 1275 ms 31060 KB Output is correct
9 Correct 4544 ms 28044 KB Output is correct
10 Correct 3364 ms 59836 KB Output is correct
11 Execution timed out 8010 ms 53952 KB Time limit exceeded
12 Correct 2267 ms 17820 KB Output is correct
13 Correct 3164 ms 17980 KB Output is correct
14 Correct 4435 ms 24216 KB Output is correct
15 Correct 6140 ms 22056 KB Output is correct
16 Correct 5446 ms 27640 KB Output is correct
17 Correct 4710 ms 32932 KB Output is correct