oj.uz

Submission #116574

# Submission time Handle Problem Language Result Execution time Memory
116574 2019-06-13T00:38:43 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 43484 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=447;
vector<int> adj[200000], R[25000];
int node_cnt, 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<=200000;n+=n&-n) tree[n]+=v;
}
 
int get_sum(int n)
{
	int ret=0;
	for(;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 5760 KB Output is correct
2 Correct 6 ms 5760 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 10 ms 5760 KB Output is correct
5 Correct 14 ms 5632 KB Output is correct
6 Correct 26 ms 5760 KB Output is correct
7 Correct 21 ms 5632 KB Output is correct
8 Correct 30 ms 5760 KB Output is correct
9 Correct 62 ms 6144 KB Output is correct
10 Correct 57 ms 6144 KB Output is correct
11 Correct 192 ms 6528 KB Output is correct
12 Correct 190 ms 6932 KB Output is correct
13 Correct 176 ms 6528 KB Output is correct
14 Correct 301 ms 7040 KB Output is correct
15 Correct 384 ms 9008 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1675 ms 11012 KB Output is correct
2 Correct 2009 ms 9708 KB Output is correct
3 Correct 4128 ms 12756 KB Output is correct
4 Correct 356 ms 7216 KB Output is correct
5 Correct 531 ms 8448 KB Output is correct
6 Correct 649 ms 15792 KB Output is correct
7 Correct 2221 ms 12536 KB Output is correct
8 Correct 1280 ms 31608 KB Output is correct
9 Correct 4998 ms 14072 KB Output is correct
10 Correct 5403 ms 43484 KB Output is correct
11 Execution timed out 8036 ms 13944 KB Time limit exceeded
12 Correct 2116 ms 17872 KB Output is correct
13 Correct 3266 ms 18044 KB Output is correct
14 Correct 4373 ms 24584 KB Output is correct
15 Correct 4879 ms 22136 KB Output is correct
16 Correct 5721 ms 27724 KB Output is correct
17 Correct 5363 ms 33084 KB Output is correct