oj.uz

Submission #116561

# Submission time Handle Problem Language Result Execution time Memory
116561 2019-06-13T00:07:16 Z kig9981 Regions (IOI09_regions) C++17
75 / 100
 8000 ms 131072 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=200;
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][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 6 ms 5632 KB Output is correct
2 Correct 7 ms 5760 KB Output is correct
3 Correct 9 ms 5760 KB Output is correct
4 Correct 9 ms 5632 KB Output is correct
5 Correct 9 ms 5632 KB Output is correct
6 Correct 13 ms 5632 KB Output is correct
7 Correct 38 ms 5676 KB Output is correct
8 Correct 44 ms 5760 KB Output is correct
9 Correct 66 ms 6144 KB Output is correct
10 Correct 81 ms 6144 KB Output is correct
11 Correct 151 ms 6400 KB Output is correct
12 Correct 154 ms 6784 KB Output is correct
13 Correct 172 ms 6564 KB Output is correct
14 Correct 451 ms 7088 KB Output is correct
15 Correct 374 ms 9984 KB Output is correct

Subtask #2
60.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1100 ms 11512 KB Output is correct
2 Correct 1046 ms 11096 KB Output is correct
3 Correct 1670 ms 14780 KB Output is correct
4 Correct 485 ms 7168 KB Output is correct
5 Correct 348 ms 8356 KB Output is correct
6 Correct 517 ms 15648 KB Output is correct
7 Correct 1142 ms 19448 KB Output is correct
8 Correct 993 ms 31096 KB Output is correct
9 Correct 3835 ms 39484 KB Output is correct
10 Runtime error 1651 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 5606 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Execution timed out 8026 ms 67528 KB Time limit exceeded
13 Execution timed out 8015 ms 97740 KB Time limit exceeded
14 Correct 3721 ms 27420 KB Output is correct
15 Correct 5731 ms 22156 KB Output is correct
16 Runtime error 2493 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 5052 ms 36204 KB Output is correct