oj.uz

Submission #116438

# Submission time Handle Problem Language Result Execution time Memory
116438 2019-06-12T12:58:48 Z kig9981 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 131072 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=400;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[200000/rt][200000], sum2[200000/rt][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 idx)
{
	if(RV[c]==O[idx]) {
		sum[idx][c]++;
		sum2[idx][c]++;
	}
	for(auto n: adj[c]) {
		sum[idx][n]=sum[idx][c];
		dfs2(n,idx);
		sum2[idx][c]+=sum2[idx][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) {
		O.push_back(i);
		dfs2(0,O.size()-1);
	}
	for(int i=0;i<O.size();i++) for(int j=0;j<N;j++) {
		ans[i][RV[j]].first+=sum[i][j];
		ans[i][RV[j]].second+=sum2[i][j];
	}
	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;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<O.size();i++) for(int j=0;j<N;j++) {
              ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5632 KB Output is correct
2 Correct 6 ms 5632 KB Output is correct
3 Correct 9 ms 5680 KB Output is correct
4 Correct 8 ms 5632 KB Output is correct
5 Correct 15 ms 5700 KB Output is correct
6 Correct 29 ms 5632 KB Output is correct
7 Correct 27 ms 5752 KB Output is correct
8 Correct 20 ms 5788 KB Output is correct
9 Correct 68 ms 6080 KB Output is correct
10 Correct 53 ms 6264 KB Output is correct
11 Correct 220 ms 6400 KB Output is correct
12 Correct 129 ms 6924 KB Output is correct
13 Correct 188 ms 6568 KB Output is correct
14 Correct 372 ms 7040 KB Output is correct
15 Correct 381 ms 8968 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1560 ms 21352 KB Output is correct
2 Correct 1824 ms 17192 KB Output is correct
3 Correct 3583 ms 18488 KB Output is correct
4 Correct 373 ms 7100 KB Output is correct
5 Correct 433 ms 8192 KB Output is correct
6 Correct 529 ms 40184 KB Output is correct
7 Correct 1952 ms 28536 KB Output is correct
8 Correct 1377 ms 108388 KB Output is correct
9 Correct 4897 ms 13992 KB Output is correct
10 Runtime error 870 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Execution timed out 8068 ms 14000 KB Time limit exceeded
12 Correct 2358 ms 19224 KB Output is correct
13 Correct 2834 ms 19108 KB Output is correct
14 Correct 4056 ms 56952 KB Output is correct
15 Correct 6299 ms 22520 KB Output is correct
16 Correct 6936 ms 25964 KB Output is correct
17 Correct 5969 ms 64772 KB Output is correct