Submission #116437

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
116437	2019-06-12T12:57:32 Z	kig9981	Regions (IOI09_regions)	C++17	90 / 100	8000 ms	64524 KB

regions

#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=500;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[200000/rt][200000], sum2[200000/rt][200000], tree[200001];
pair<long long,long long> ans[200000/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	5760 KB	Output is correct
2	Correct	7 ms	5680 KB	Output is correct
3	Correct	8 ms	5660 KB	Output is correct
4	Correct	12 ms	5632 KB	Output is correct
5	Correct	10 ms	5680 KB	Output is correct
6	Correct	14 ms	5632 KB	Output is correct
7	Correct	19 ms	5680 KB	Output is correct
8	Correct	23 ms	5760 KB	Output is correct
9	Correct	32 ms	6064 KB	Output is correct
10	Correct	98 ms	6144 KB	Output is correct
11	Correct	102 ms	6448 KB	Output is correct
12	Correct	120 ms	6784 KB	Output is correct
13	Correct	157 ms	6528 KB	Output is correct
14	Correct	348 ms	7048 KB	Output is correct
15	Correct	368 ms	8824 KB	Output is correct

Subtask #2

75.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1666 ms	17040 KB	Output is correct
2	Correct	1557 ms	17420 KB	Output is correct
3	Correct	3601 ms	18540 KB	Output is correct
4	Correct	391 ms	7168 KB	Output is correct
5	Correct	563 ms	8320 KB	Output is correct
6	Correct	1506 ms	18304 KB	Output is correct
7	Correct	3066 ms	9152 KB	Output is correct
8	Correct	2963 ms	15868 KB	Output is correct
9	Correct	5024 ms	13944 KB	Output is correct
10	Execution timed out	8031 ms	17400 KB	Time limit exceeded
11	Execution timed out	8073 ms	13992 KB	Time limit exceeded
12	Correct	2640 ms	19208 KB	Output is correct
13	Correct	3983 ms	19104 KB	Output is correct
14	Correct	4481 ms	57052 KB	Output is correct
15	Correct	5567 ms	22556 KB	Output is correct
16	Correct	6150 ms	25964 KB	Output is correct
17	Correct	5523 ms	64524 KB	Output is correct