oj.uz

Submission #116565

# Submission time Handle Problem Language Result Execution time Memory
116565 2019-06-13T00:12:49 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 41696 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

#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=448;
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 5760 KB Output is correct
2 Correct 7 ms 5632 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 12 ms 5632 KB Output is correct
5 Correct 17 ms 5760 KB Output is correct
6 Correct 21 ms 5760 KB Output is correct
7 Correct 23 ms 5760 KB Output is correct
8 Correct 45 ms 5760 KB Output is correct
9 Correct 53 ms 6144 KB Output is correct
10 Correct 80 ms 6144 KB Output is correct
11 Correct 168 ms 6400 KB Output is correct
12 Correct 175 ms 6912 KB Output is correct
13 Correct 272 ms 6656 KB Output is correct
14 Correct 433 ms 7040 KB Output is correct
15 Correct 469 ms 8760 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1456 ms 10536 KB Output is correct
2 Correct 1875 ms 9592 KB Output is correct
3 Correct 3645 ms 12024 KB Output is correct
4 Correct 400 ms 7108 KB Output is correct
5 Correct 496 ms 8320 KB Output is correct
6 Correct 682 ms 15480 KB Output is correct
7 Correct 1966 ms 12332 KB Output is correct
8 Correct 954 ms 29860 KB Output is correct
9 Correct 4505 ms 14200 KB Output is correct
10 Correct 5052 ms 41696 KB Output is correct
11 Execution timed out 8064 ms 13972 KB Time limit exceeded
12 Correct 2152 ms 17660 KB Output is correct
13 Correct 3079 ms 17544 KB Output is correct
14 Correct 3642 ms 24152 KB Output is correct
15 Correct 4815 ms 20860 KB Output is correct
16 Correct 5913 ms 23992 KB Output is correct
17 Correct 5249 ms 29892 KB Output is correct