oj.uz

Submission #116416

# Submission time Handle Problem Language Result Execution time Memory
116416 2019-06-12T12:13:15 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 118056 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

#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:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<O.size()-1;j++) {
               ~^~~~~~~~~~~
regions.cpp:82: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 5760 KB Output is correct
2 Correct 7 ms 5632 KB Output is correct
3 Correct 7 ms 5760 KB Output is correct
4 Correct 9 ms 5760 KB Output is correct
5 Correct 14 ms 5680 KB Output is correct
6 Correct 27 ms 5760 KB Output is correct
7 Correct 19 ms 5760 KB Output is correct
8 Correct 34 ms 5760 KB Output is correct
9 Correct 59 ms 6032 KB Output is correct
10 Correct 125 ms 6260 KB Output is correct
11 Correct 168 ms 6400 KB Output is correct
12 Correct 150 ms 6920 KB Output is correct
13 Correct 150 ms 6672 KB Output is correct
14 Correct 427 ms 7036 KB Output is correct
15 Correct 492 ms 8824 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1392 ms 19504 KB Output is correct
2 Correct 1847 ms 17312 KB Output is correct
3 Correct 3468 ms 18472 KB Output is correct
4 Correct 357 ms 7192 KB Output is correct
5 Correct 282 ms 8320 KB Output is correct
6 Correct 674 ms 40080 KB Output is correct
7 Correct 2378 ms 20680 KB Output is correct
8 Correct 1444 ms 108288 KB Output is correct
9 Correct 5217 ms 13996 KB Output is correct
10 Correct 5023 ms 118056 KB Output is correct
11 Execution timed out 8010 ms 13900 KB Time limit exceeded
12 Correct 2596 ms 19192 KB Output is correct
13 Correct 3329 ms 19112 KB Output is correct
14 Correct 4021 ms 56960 KB Output is correct
15 Correct 5763 ms 22560 KB Output is correct
16 Correct 5940 ms 26012 KB Output is correct
17 Correct 5756 ms 64628 KB Output is correct