oj.uz

Submission #116415

# Submission time Handle Problem Language Result Execution time Memory
116415 2019-06-12T12:12:41 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 7690 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=350;
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 5760 KB Output is correct
2 Correct 6 ms 5632 KB Output is correct
3 Correct 8 ms 5760 KB Output is correct
4 Correct 11 ms 5760 KB Output is correct
5 Correct 14 ms 5760 KB Output is correct
6 Correct 25 ms 5632 KB Output is correct
7 Correct 17 ms 5760 KB Output is correct
8 Correct 24 ms 5760 KB Output is correct
9 Correct 29 ms 6144 KB Output is correct
10 Correct 54 ms 6168 KB Output is correct
11 Correct 96 ms 6400 KB Output is correct
12 Correct 163 ms 6784 KB Output is correct
13 Correct 234 ms 6528 KB Output is correct
14 Correct 435 ms 7040 KB Output is correct
15 Correct 468 ms 8960 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1597 ms 22044 KB Output is correct
2 Correct 1648 ms 17400 KB Output is correct
3 Correct 3427 ms 20216 KB Output is correct
4 Correct 366 ms 7168 KB Output is correct
5 Correct 474 ms 8440 KB Output is correct
6 Correct 585 ms 40472 KB Output is correct
7 Correct 1715 ms 34680 KB Output is correct
8 Correct 1522 ms 111864 KB Output is correct
9 Correct 5724 ms 14036 KB Output is correct
10 Runtime error 764 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Correct 7690 ms 14012 KB Output is correct
12 Correct 2100 ms 19336 KB Output is correct
13 Correct 3390 ms 20084 KB Output is correct
14 Correct 4682 ms 57344 KB Output is correct
15 Correct 5684 ms 25928 KB Output is correct
16 Correct 5087 ms 35192 KB Output is correct
17 Correct 5799 ms 72584 KB Output is correct