oj.uz

Submission #116432

# Submission time Handle Problem Language Result Execution time Memory
116432 2019-06-12T12:54:19 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 118192 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 i=0;i<O.size();i++) for(int j=0;j<N;j++) {
		ans[i][RV[j]].first+=sum[i][j];
		ans[i][RV[j]].second+=sum2[i][j];
	}
	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:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<O.size();i++) for(int j=0;j<N;j++) {
              ~^~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5640 KB Output is correct
2 Correct 7 ms 5760 KB Output is correct
3 Correct 8 ms 5632 KB Output is correct
4 Correct 11 ms 5632 KB Output is correct
5 Correct 10 ms 5760 KB Output is correct
6 Correct 28 ms 5760 KB Output is correct
7 Correct 29 ms 5632 KB Output is correct
8 Correct 50 ms 5788 KB Output is correct
9 Correct 41 ms 6016 KB Output is correct
10 Correct 57 ms 6180 KB Output is correct
11 Correct 99 ms 6444 KB Output is correct
12 Correct 168 ms 6724 KB Output is correct
13 Correct 207 ms 6676 KB Output is correct
14 Correct 398 ms 7168 KB Output is correct
15 Correct 410 ms 8724 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1602 ms 19576 KB Output is correct
2 Correct 1927 ms 17260 KB Output is correct
3 Correct 3813 ms 18460 KB Output is correct
4 Correct 423 ms 7168 KB Output is correct
5 Correct 417 ms 8312 KB Output is correct
6 Correct 645 ms 40136 KB Output is correct
7 Correct 1963 ms 20664 KB Output is correct
8 Correct 1324 ms 108272 KB Output is correct
9 Correct 5293 ms 13992 KB Output is correct
10 Correct 5806 ms 118192 KB Output is correct
11 Execution timed out 8070 ms 13944 KB Time limit exceeded
12 Correct 2005 ms 19200 KB Output is correct
13 Correct 3592 ms 19244 KB Output is correct
14 Correct 3904 ms 57104 KB Output is correct
15 Correct 6106 ms 22580 KB Output is correct
16 Correct 5789 ms 25896 KB Output is correct
17 Correct 5585 ms 64624 KB Output is correct