Submission #764157

#	Time	Username	Problem	Language	Result	Execution time	Memory
764157		a_aguilo	Regions (IOI09_regions)	C++14	4 / 100	8087 ms	50000 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;
vector<int> visited;
int enter[200000];
int out[200000];
unordered_map<int, int> freqRegions;

void dfs(int node){
	visited[node] = 1;
	//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));
	pair<pair<int, int>, pair<int, int>> queries[N];
	for(int i = 0; i < N; ++i){
		queries[i] = {{enter[i]/SQRT, -out[i]}, {enter[i], i}};
	}
	sort(queries, queries+N);
	int left = 0; int right = 0;
	freqRegions[EulerTours[0]] = 1;
	for(int i = 0; i < N; ++i){
		int qR = - queries[i].first.second;
		int qL = queries[i].second.first;
		while(right < qR){
			right++;
			r = region[EulerTours[right]];
			freqRegions[r]++;
		}while(right > qR){
			r = region[EulerTours[right]];
			freqRegions[r]--;
			right--;
		}
		while(left < qL){
			r = region[EulerTours[left]];
			freqRegions[r]--;
			left++;
		}while(left > qL){
			left--;
			r = region[EulerTours[left]];
			freqRegions[r]++;
		}
		int actualReg = region[queries[i].second.second];
		for(int i = 0; i < R; ++i){
			dp[actualReg][i] += freqRegions[i];
		}
	}
	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];
			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]--;
	}
	visited = vector<int>(N, 0);
	dfs(0);
	/*
	for(int i = 0; i < N; ++i) cout << EulerTours[i] << " ";
		cout << endl;*/
	/*
	if(R <= 500) rSmall();
	else rBig();*/
	rBig();
	return 0;
}

Compilation message (stderr)

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

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