oj.uz

Submission #116573

# Submission time Handle Problem Language Result Execution time Memory
116573 2019-06-13T00:34:13 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 41748 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];
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 7 ms 5760 KB Output is correct
2 Correct 6 ms 5632 KB Output is correct
3 Correct 9 ms 5760 KB Output is correct
4 Correct 9 ms 5760 KB Output is correct
5 Correct 14 ms 5760 KB Output is correct
6 Correct 17 ms 5632 KB Output is correct
7 Correct 31 ms 5760 KB Output is correct
8 Correct 22 ms 5760 KB Output is correct
9 Correct 62 ms 6144 KB Output is correct
10 Correct 99 ms 6188 KB Output is correct
11 Correct 162 ms 6448 KB Output is correct
12 Correct 157 ms 6784 KB Output is correct
13 Correct 226 ms 6528 KB Output is correct
14 Correct 397 ms 7040 KB Output is correct
15 Correct 468 ms 8832 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1556 ms 10536 KB Output is correct
2 Correct 1896 ms 9720 KB Output is correct
3 Correct 3746 ms 12072 KB Output is correct
4 Correct 365 ms 7160 KB Output is correct
5 Correct 357 ms 8312 KB Output is correct
6 Correct 614 ms 15736 KB Output is correct
7 Correct 2192 ms 12512 KB Output is correct
8 Correct 1382 ms 30404 KB Output is correct
9 Correct 4643 ms 13988 KB Output is correct
10 Correct 5157 ms 41748 KB Output is correct
11 Execution timed out 8071 ms 14052 KB Time limit exceeded
12 Correct 2238 ms 17668 KB Output is correct
13 Correct 2851 ms 17616 KB Output is correct
14 Correct 3667 ms 24252 KB Output is correct
15 Correct 5948 ms 20868 KB Output is correct
16 Correct 5119 ms 24084 KB Output is correct
17 Correct 5623 ms 30064 KB Output is correct