oj.uz

Submission #116402

# Submission time Handle Problem Language Result Execution time Memory
116402 2019-06-12T11:58:44 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 122536 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 j=0;j<O.size()-1;j++) {
			for(auto r: R[O[j]]) ans[O.size()-1][O[j]].first+=sum[O.size()-1][r];
			for(auto r: R[i]) ans[j][i].first+=sum[j][r];
		}
	}
	for(int i=0;i<O.size();i++) {
		for(int j=0;j<M;j++) if(R[j].size()<rt) for(auto r: R[j]) {
			ans[i][j].first+=sum[i][r];
			ans[i][j].second+=sum2[i][r];
		}
	}
	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:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<O.size()-1;j++) {
               ~^~~~~~~~~~~
regions.cpp:79:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<O.size();i++) {
              ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5632 KB Output is correct
2 Correct 6 ms 5760 KB Output is correct
3 Correct 8 ms 5760 KB Output is correct
4 Correct 11 ms 5632 KB Output is correct
5 Correct 9 ms 5632 KB Output is correct
6 Correct 25 ms 5760 KB Output is correct
7 Correct 17 ms 5660 KB Output is correct
8 Correct 19 ms 5784 KB Output is correct
9 Correct 38 ms 6108 KB Output is correct
10 Correct 127 ms 6144 KB Output is correct
11 Correct 152 ms 6400 KB Output is correct
12 Correct 153 ms 6784 KB Output is correct
13 Correct 147 ms 6592 KB Output is correct
14 Correct 388 ms 7160 KB Output is correct
15 Correct 449 ms 8960 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1715 ms 20276 KB Output is correct
2 Correct 1997 ms 17408 KB Output is correct
3 Correct 3819 ms 20216 KB Output is correct
4 Correct 406 ms 7168 KB Output is correct
5 Correct 489 ms 8360 KB Output is correct
6 Correct 824 ms 40312 KB Output is correct
7 Correct 2441 ms 20984 KB Output is correct
8 Correct 1473 ms 111708 KB Output is correct
9 Correct 4592 ms 14128 KB Output is correct
10 Correct 5663 ms 122536 KB Output is correct
11 Execution timed out 8077 ms 13944 KB Time limit exceeded
12 Correct 2075 ms 19348 KB Output is correct
13 Correct 2998 ms 20092 KB Output is correct
14 Correct 4210 ms 57540 KB Output is correct
15 Correct 5494 ms 25848 KB Output is correct
16 Correct 5920 ms 35192 KB Output is correct
17 Correct 5440 ms 72652 KB Output is correct