oj.uz

Submission #116411

# Submission time Handle Problem Language Result Execution time Memory
116411 2019-06-12T12:10:42 Z kig9981 Regions (IOI09_regions) C++17
90 / 100
 6272 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=300;
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 7 ms 5632 KB Output is correct
3 Correct 7 ms 5760 KB Output is correct
4 Correct 14 ms 5632 KB Output is correct
5 Correct 15 ms 5760 KB Output is correct
6 Correct 26 ms 5632 KB Output is correct
7 Correct 17 ms 5760 KB Output is correct
8 Correct 32 ms 5876 KB Output is correct
9 Correct 42 ms 6032 KB Output is correct
10 Correct 74 ms 6144 KB Output is correct
11 Correct 126 ms 6456 KB Output is correct
12 Correct 152 ms 6828 KB Output is correct
13 Correct 185 ms 6528 KB Output is correct
14 Correct 376 ms 7084 KB Output is correct
15 Correct 446 ms 8972 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1231 ms 24476 KB Output is correct
2 Correct 1929 ms 17332 KB Output is correct
3 Correct 3151 ms 20160 KB Output is correct
4 Correct 352 ms 7060 KB Output is correct
5 Correct 414 ms 8388 KB Output is correct
6 Correct 501 ms 40348 KB Output is correct
7 Correct 1487 ms 45380 KB Output is correct
8 Correct 1456 ms 111712 KB Output is correct
9 Correct 4996 ms 88824 KB Output is correct
10 Runtime error 747 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 1525 ms 131072 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Correct 2378 ms 19336 KB Output is correct
13 Correct 3326 ms 20092 KB Output is correct
14 Correct 4191 ms 57392 KB Output is correct
15 Correct 5318 ms 25944 KB Output is correct
16 Correct 6272 ms 35224 KB Output is correct
17 Correct 4768 ms 72628 KB Output is correct