oj.uz

Submission #116413

# Submission time Handle Problem Language Result Execution time Memory
116413 2019-06-12T12:10:54 Z kig9981 Regions (IOI09_regions) C++17
90 / 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=400;
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 7 ms 5680 KB Output is correct
2 Correct 6 ms 5680 KB Output is correct
3 Correct 9 ms 5760 KB Output is correct
4 Correct 9 ms 5760 KB Output is correct
5 Correct 14 ms 5632 KB Output is correct
6 Correct 24 ms 5632 KB Output is correct
7 Correct 19 ms 5760 KB Output is correct
8 Correct 37 ms 5760 KB Output is correct
9 Correct 38 ms 6016 KB Output is correct
10 Correct 53 ms 6144 KB Output is correct
11 Correct 155 ms 6400 KB Output is correct
12 Correct 116 ms 6784 KB Output is correct
13 Correct 224 ms 6656 KB Output is correct
14 Correct 415 ms 7040 KB Output is correct
15 Correct 390 ms 8972 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1242 ms 21996 KB Output is correct
2 Correct 1829 ms 17336 KB Output is correct
3 Correct 3526 ms 20348 KB Output is correct
4 Correct 410 ms 7168 KB Output is correct
5 Correct 552 ms 8448 KB Output is correct
6 Correct 506 ms 40440 KB Output is correct
7 Correct 2227 ms 28916 KB Output is correct
8 Correct 1504 ms 111820 KB Output is correct
9 Correct 4996 ms 14100 KB Output is correct
10 Runtime error 671 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Execution timed out 8031 ms 13992 KB Time limit exceeded
12 Correct 2760 ms 19388 KB Output is correct
13 Correct 3212 ms 20032 KB Output is correct
14 Correct 3923 ms 57368 KB Output is correct
15 Correct 6622 ms 25848 KB Output is correct
16 Correct 6436 ms 35172 KB Output is correct
17 Correct 5591 ms 72640 KB Output is correct