Submission #764194

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
764194	2023-06-23T08:30:52 Z	a_aguilo	Regions (IOI09_regions)	C++14	40 / 100	8000 ms	25276 KB

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

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

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	2 ms	208 KB	Output is correct
4	Correct	4 ms	208 KB	Output is correct
5	Correct	7 ms	336 KB	Output is correct
6	Correct	12 ms	336 KB	Output is correct
7	Correct	28 ms	336 KB	Output is correct
8	Correct	33 ms	464 KB	Output is correct
9	Correct	48 ms	848 KB	Output is correct
10	Correct	76 ms	1104 KB	Output is correct
11	Correct	147 ms	1428 KB	Output is correct
12	Correct	196 ms	2000 KB	Output is correct
13	Correct	285 ms	1736 KB	Output is correct
14	Correct	630 ms	2552 KB	Output is correct
15	Correct	659 ms	5308 KB	Output is correct

Subtask #2

25.0 / 85.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	8064 ms	6592 KB	Time limit exceeded
2	Execution timed out	8023 ms	5576 KB	Time limit exceeded
3	Execution timed out	8061 ms	8768 KB	Time limit exceeded
4	Correct	280 ms	2640 KB	Output is correct
5	Correct	368 ms	4488 KB	Output is correct
6	Execution timed out	8019 ms	4476 KB	Time limit exceeded
7	Correct	4362 ms	5896 KB	Output is correct
8	Correct	2547 ms	11496 KB	Output is correct
9	Correct	4019 ms	13012 KB	Output is correct
10	Execution timed out	8061 ms	18492 KB	Time limit exceeded
11	Execution timed out	8023 ms	14012 KB	Time limit exceeded
12	Execution timed out	8093 ms	15304 KB	Time limit exceeded
13	Execution timed out	8076 ms	15564 KB	Time limit exceeded
14	Execution timed out	8079 ms	15552 KB	Time limit exceeded
15	Execution timed out	8045 ms	19824 KB	Time limit exceeded
16	Execution timed out	8007 ms	25276 KB	Time limit exceeded
17	Execution timed out	8101 ms	24040 KB	Time limit exceeded