Submission #764194

#	Time	Username	Problem	Language	Result	Execution time	Memory
764194		a_aguilo	Regions (IOI09_regions)	C++14	40 / 100	8101 ms	25276 KiB

regions

#include<bits/stdc++.h>

using namespace std;

int N, R, Q;
int SQRT = 450;
int region[200000];
vector<vector<int>> AdjList;
vector<int> EulerTours;
int enter[200000];
int out[200000];
//unordered_map<int, int> freqRegions;

void dfs(int node){
	//cout << node << endl;
	EulerTours.push_back(node);
	enter[node] = EulerTours.size()-1;
	for(int son: AdjList[node]){
		dfs(son);
	}
	out[node] = EulerTours.size()-1;
}

/*

void rSmall(){
	int r;
	freqRegions.reserve(512);
	vector<vector<int>> dp(R, vector<int>(R, 0));
	preProcess(0, dp);
	int r1, r2;
	while(Q--){
		cin >> r1 >> r2;
		r1--; r2--;
		cout << dp[r1][r2] << endl;
	}
}*/

void rBig(){
	//vector<map<int, int>> blocks(500);
	vector<vector<int>> employees(R);
	for(int i = 0; i < N; ++i){
		employees[region[i]].push_back(i);
		int B = i/SQRT;
		//blocks[R][region[EulerTours[i]]]++;
	}
	int r1, r2;
	while(Q--){
		cin >> r1 >> r2;
		r1--; r2--;
		int ans = 0;
		for(int i: employees[r1]){
			for(int j: employees[r2]){
				if(enter[i]<enter[j] && out[i]>=out[j])ans++;
			}
		}
		cout << ans << endl;
	}
}

int main(){
	int p;
	cin >> N >> R >> Q;
	AdjList = vector<vector<int>>(N);
	for(int i = 0; i < N; ++i){
		
		if(i){
			cin >> p;
			p--;
			AdjList[p].push_back(i);
		}
		cin >> region[i];
		region[i]--;
	}
	dfs(0);
	/*
	for(int i = 0; i < N; ++i) cout << EulerTours[i] << " ";
		cout << endl;*/
	/*
	if(R <= 1000) rSmall();
	else rBig();*/
	rBig();
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void rBig()':
regions.cpp:44:7: warning: unused variable 'B' [-Wunused-variable]
   44 |   int B = i/SQRT;
      |       ^

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