oj.uz

Submission #116571

# Submission time Handle Problem Language Result Execution time Memory
116571 2019-06-13T00:25:51 Z kig9981 Regions (IOI09_regions) C++17
100 / 100
 7220 ms 43380 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=448;
vector<int> adj[200000], R[25000];
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[200000], sum2[200000], tree[200001], idx[200000];
long long ans[rt][25000], ans2[rt][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, sz=0;
	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[sz][RV[j]]+=sum[j];
			ans2[sz][RV[j]]+=sum2[j];
		}
		idx[i]=sz++;
	}
	while(Q--) {
		int a, b;
		cin>>a>>b; --a; --b;
		if(R[a].size()>=rt) cout<<ans[idx[a]][b]<<'\n';
		else if(R[b].size()>=rt) cout<<ans2[idx[b]][a]<<'\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 7 ms 5632 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 11 ms 5760 KB Output is correct
5 Correct 14 ms 5760 KB Output is correct
6 Correct 19 ms 5632 KB Output is correct
7 Correct 18 ms 5632 KB Output is correct
8 Correct 19 ms 5760 KB Output is correct
9 Correct 56 ms 6144 KB Output is correct
10 Correct 76 ms 6144 KB Output is correct
11 Correct 166 ms 6448 KB Output is correct
12 Correct 115 ms 6912 KB Output is correct
13 Correct 156 ms 6528 KB Output is correct
14 Correct 331 ms 7200 KB Output is correct
15 Correct 499 ms 8952 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1656 ms 10872 KB Output is correct
2 Correct 1991 ms 9792 KB Output is correct
3 Correct 3956 ms 12792 KB Output is correct
4 Correct 472 ms 7168 KB Output is correct
5 Correct 536 ms 8368 KB Output is correct
6 Correct 736 ms 15992 KB Output is correct
7 Correct 2253 ms 12536 KB Output is correct
8 Correct 920 ms 31632 KB Output is correct
9 Correct 4536 ms 14072 KB Output is correct
10 Correct 5100 ms 43380 KB Output is correct
11 Correct 7220 ms 14016 KB Output is correct
12 Correct 2169 ms 17976 KB Output is correct
13 Correct 2904 ms 17928 KB Output is correct
14 Correct 4150 ms 24380 KB Output is correct
15 Correct 5648 ms 22136 KB Output is correct
16 Correct 5291 ms 27688 KB Output is correct
17 Correct 4761 ms 33176 KB Output is correct