Submission #116385

#	Time	Username	Problem	Language	Result	Execution time	Memory
116385		kig9981	Regions (IOI09_regions)	C++17	45 / 100	8050 ms	131072 KiB

regions

#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, SZ=1<<18;
vector<int> adj[200000], R[25000], O;
int node_cnt=-1, RV[200000], num[200000], fin[200000], sum[rt][200000], tree[rt+1][2*SZ];
pair<long long,long long> ans[rt][25000];

void add_tree(int idx, int n, int v)
{
	for(tree[idx][n+=SZ]+=v;n>>=1;) tree[idx][n]=tree[idx][2*n]+tree[idx][2*n+1];
}

int get_sum(int idx, int s, int e)
{
	int ret=0;
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) ret+=tree[idx][s++];
		if(~e&1) ret+=tree[idx][e--];
	}
	return ret;
}

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

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[i]) ans[O.size()-1][O[j]].first+=sum[j][r];
			for(auto r: R[O[j]]) ans[j][O.back()].first+=sum[O.size()-1][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+=get_sum(i,num[r],fin[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(rt,num[r],1);
			for(auto r: R[a]) ans+=get_sum(rt,num[r],fin[r]);
			for(auto r: R[b]) add_tree(rt,num[r],-1);
			cout<<ans<<'\n';
		}
		cout.flush();
	}
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<O.size()-1;j++) {
               ~^~~~~~~~~~~
regions.cpp:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  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]) {
              ~^~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 30 / 85