oj.uz

Submission #116419

# Submission time Handle Problem Language Result Execution time Memory
116419 2019-06-12T12:21:28 Z kig9981 Regions (IOI09_regions) C++17
100 / 100
 7786 ms 122488 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], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[rt][200000], sum2[rt][200000], tree[200001];
pair<long long,long long> ans[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:75: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 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 12 ms 5632 KB Output is correct
5 Correct 14 ms 5760 KB Output is correct
6 Correct 22 ms 5632 KB Output is correct
7 Correct 26 ms 5632 KB Output is correct
8 Correct 37 ms 5668 KB Output is correct
9 Correct 79 ms 6016 KB Output is correct
10 Correct 104 ms 6144 KB Output is correct
11 Correct 155 ms 6400 KB Output is correct
12 Correct 160 ms 6912 KB Output is correct
13 Correct 312 ms 6656 KB Output is correct
14 Correct 362 ms 7156 KB Output is correct
15 Correct 488 ms 8956 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1716 ms 20284 KB Output is correct
2 Correct 2021 ms 17400 KB Output is correct
3 Correct 3726 ms 20216 KB Output is correct
4 Correct 370 ms 7160 KB Output is correct
5 Correct 598 ms 8444 KB Output is correct
6 Correct 785 ms 40436 KB Output is correct
7 Correct 2174 ms 20984 KB Output is correct
8 Correct 1337 ms 111732 KB Output is correct
9 Correct 4507 ms 14264 KB Output is correct
10 Correct 5638 ms 122488 KB Output is correct
11 Correct 7786 ms 14016 KB Output is correct
12 Correct 2213 ms 19320 KB Output is correct
13 Correct 3085 ms 20088 KB Output is correct
14 Correct 3746 ms 57448 KB Output is correct
15 Correct 5826 ms 26012 KB Output is correct
16 Correct 5160 ms 35340 KB Output is correct
17 Correct 5632 ms 72592 KB Output is correct