oj.uz

Submission #116407

# Submission time Handle Problem Language Result Execution time Memory
116407 2019-06-12T12:06:42 Z kig9981 Regions (IOI09_regions) C++17
65 / 100
 6296 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=200;
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 5632 KB Output is correct
2 Correct 6 ms 5632 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 11 ms 5632 KB Output is correct
5 Correct 12 ms 5760 KB Output is correct
6 Correct 30 ms 5632 KB Output is correct
7 Correct 39 ms 5632 KB Output is correct
8 Correct 34 ms 5760 KB Output is correct
9 Correct 54 ms 6016 KB Output is correct
10 Correct 127 ms 6192 KB Output is correct
11 Correct 171 ms 6444 KB Output is correct
12 Correct 155 ms 6780 KB Output is correct
13 Correct 242 ms 6568 KB Output is correct
14 Correct 346 ms 7088 KB Output is correct
15 Correct 422 ms 11128 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 71764 KB Output is correct
2 Correct 1084 ms 114152 KB Output is correct
3 Runtime error 503 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Correct 400 ms 7160 KB Output is correct
5 Correct 497 ms 8368 KB Output is correct
6 Correct 586 ms 40336 KB Output is correct
7 Correct 1432 ms 52504 KB Output is correct
8 Correct 1373 ms 111756 KB Output is correct
9 Runtime error 1963 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 710 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 1524 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 3186 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 1804 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Correct 3935 ms 76116 KB Output is correct
15 Correct 5877 ms 25960 KB Output is correct
16 Runtime error 794 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Correct 6296 ms 91436 KB Output is correct