oj.uz

Submission #116420

# Submission time Handle Problem Language Result Execution time Memory
116420 2019-06-12T12:29:09 Z kig9981 Regions (IOI09_regions) C++17
100 / 100
 7954 ms 122568 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], idx[200000];
long long ans1[rt][25000], ans2[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) {
		idx[i]=O.size();
		O.push_back(i);
		dfs2(0,O.size()-1);
	}
	for(int i=0;i<O.size();i++) for(int j=0;j<N;j++) {
		ans1[i][RV[j]]+=sum[i][j];
		ans2[i][RV[j]]+=sum2[i][j];
	}
	while(Q--) {
		int a, b;
		cin>>a>>b; --a; --b;
		if(R[a].size()>=rt) cout<<ans1[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;
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:76: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 5760 KB Output is correct
2 Correct 7 ms 5760 KB Output is correct
3 Correct 7 ms 5632 KB Output is correct
4 Correct 7 ms 5632 KB Output is correct
5 Correct 8 ms 5632 KB Output is correct
6 Correct 18 ms 5632 KB Output is correct
7 Correct 28 ms 5760 KB Output is correct
8 Correct 21 ms 5760 KB Output is correct
9 Correct 59 ms 6144 KB Output is correct
10 Correct 66 ms 6144 KB Output is correct
11 Correct 163 ms 6528 KB Output is correct
12 Correct 172 ms 6832 KB Output is correct
13 Correct 280 ms 6656 KB Output is correct
14 Correct 358 ms 7156 KB Output is correct
15 Correct 399 ms 8960 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1815 ms 20324 KB Output is correct
2 Correct 2017 ms 17400 KB Output is correct
3 Correct 3626 ms 20216 KB Output is correct
4 Correct 426 ms 7160 KB Output is correct
5 Correct 549 ms 8440 KB Output is correct
6 Correct 558 ms 40748 KB Output is correct
7 Correct 2403 ms 21140 KB Output is correct
8 Correct 1382 ms 112204 KB Output is correct
9 Correct 4883 ms 14092 KB Output is correct
10 Correct 4824 ms 122568 KB Output is correct
11 Correct 7954 ms 14020 KB Output is correct
12 Correct 2550 ms 19448 KB Output is correct
13 Correct 3880 ms 20024 KB Output is correct
14 Correct 3429 ms 57496 KB Output is correct
15 Correct 6616 ms 26076 KB Output is correct
16 Correct 6219 ms 35212 KB Output is correct
17 Correct 4952 ms 72888 KB Output is correct