Submission #764110

#	Time	Username	Problem	Language	Result	Execution time	Memory
764110		a_aguilo	Regions (IOI09_regions)	C++14	0 / 100	136 ms	13968 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(){
	cout << "xd" << 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);
	for(int i = 0; i < N; ++i){
		if(!visited[i]) dfs(i);
	}
	if(R <= 500) rSmall();
	else rBig();
	return 0;
}

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