Submission #764173

#	Time	Username	Problem	Language	Result	Execution time	Memory
764173		a_aguilo	Regions (IOI09_regions)	C++14	6 / 100	8090 ms	48452 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]){
			int l = enter[i] + 1;
			int r = out[i];
			//cout << i << " " << l << " " << r << endl;
			while(l % SQRT != 0 and l <= r){
				if(region[EulerTours[l]] == r2)ans++;
				l++;
			}
			int bR = r/SQRT;
			while(bR*SQRT <= r and l<=r){
				if(region[EulerTours[r]] == r2) ans++;
				r--;
			}
			int bL = l/SQRT;
			while(bL < bR){
				ans += blocks[bL][r2];
				bL++;
			}
		}
		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:43:7: warning: unused variable 'B' [-Wunused-variable]
   43 |   int B = i/SQRT;
      |       ^

• Subtask 1: 6 / 15
• Subtask 2: 0 / 85