oj.uz

Submission #116428

# Submission time Handle Problem Language Result Execution time Memory
116428 2019-06-12T12:52:29 Z kig9981 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 88588 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=448;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[rt][200000], tree[200001], idx[200000];
long long ans1[rt][25000], ans2[rt][25000];
map<pair<int,int>,long long> save;

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)
{
	sum[idx][c]+=RV[c]==O[idx];
	for(auto n: adj[c]) {
		sum[idx][n]=sum[idx][c];
		dfs2(n,idx);
	}
}

void dfs3(int c, int idx)
{
	sum[idx][c]=RV[c]==O[idx];
	for(auto n: adj[c]) {
		dfs3(n,idx);
		sum[idx][c]+=sum[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) {
		idx[i]=O.size();
		O.push_back(i);
		dfs2(0,O.size()-1);
	}
	for(int i=0;i<O.size();i++) {
		for(int j=0;j<N;j++) ans1[i][RV[j]]+=sum[i][j];
		dfs3(0,i);
		for(int j=0;j<N;j++) ans2[i][RV[j]]+=sum[i][j];
	}
	
	while(Q--) {
		int a, b;
		cin>>a>>b;
		if(save.count({--a,--b})) {
			cout<<save[{a,b}]<<endl;
			continue;
		}
		if(R[a].size()>=rt) cout<<ans1[idx[a]][b]<<'\n';
		else if(R[b].size()>=rt) cout<<ans2[idx[b]][a]<<'\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';
			save[{a,b}]=ans;
		}
		cout.flush();
	}
	return 0;
}

Compilation message

regions.cpp: In function 'int main()':
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 5732 KB Output is correct
2 Correct 6 ms 5760 KB Output is correct
3 Correct 10 ms 5632 KB Output is correct
4 Correct 8 ms 5776 KB Output is correct
5 Correct 9 ms 5716 KB Output is correct
6 Correct 27 ms 5896 KB Output is correct
7 Correct 40 ms 5800 KB Output is correct
8 Correct 37 ms 5996 KB Output is correct
9 Correct 38 ms 6368 KB Output is correct
10 Correct 101 ms 6548 KB Output is correct
11 Correct 158 ms 7108 KB Output is correct
12 Correct 165 ms 7512 KB Output is correct
13 Correct 228 ms 7464 KB Output is correct
14 Correct 376 ms 8088 KB Output is correct
15 Correct 391 ms 10028 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1546 ms 16764 KB Output is correct
2 Correct 1473 ms 14752 KB Output is correct
3 Correct 3433 ms 20168 KB Output is correct
4 Correct 551 ms 8752 KB Output is correct
5 Correct 602 ms 10664 KB Output is correct
6 Correct 836 ms 29716 KB Output is correct
7 Correct 990 ms 17816 KB Output is correct
8 Correct 1740 ms 73056 KB Output is correct
9 Correct 5388 ms 22456 KB Output is correct
10 Correct 5875 ms 88588 KB Output is correct
11 Execution timed out 8026 ms 25328 KB Time limit exceeded
12 Correct 2187 ms 20596 KB Output is correct
13 Correct 3722 ms 22552 KB Output is correct
14 Correct 4795 ms 44436 KB Output is correct
15 Correct 6136 ms 30908 KB Output is correct
16 Correct 6125 ms 37260 KB Output is correct
17 Correct 5640 ms 58852 KB Output is correct