답안 #764110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764110	2023-06-23T07:17:17 Z	a_aguilo	Regions (IOI09_regions)	C++14	0 / 100	136 ms	13968 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;
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.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	208 KB	Output isn't correct
2	Incorrect	0 ms	208 KB	Output isn't correct
3	Incorrect	1 ms	208 KB	Output isn't correct
4	Incorrect	1 ms	336 KB	Output isn't correct
5	Runtime error	1 ms	336 KB	Execution killed with signal 13
6	Runtime error	4 ms	592 KB	Execution killed with signal 13
7	Runtime error	4 ms	464 KB	Execution killed with signal 13
8	Runtime error	5 ms	592 KB	Execution killed with signal 13
9	Runtime error	12 ms	1232 KB	Execution killed with signal 13
10	Runtime error	31 ms	1864 KB	Execution killed with signal 13
11	Runtime error	47 ms	2024 KB	Execution killed with signal 13
12	Runtime error	68 ms	2996 KB	Execution killed with signal 13
13	Execution timed out	16 ms	1872 KB	Time limit exceeded (wall clock)
14	Execution timed out	18 ms	2568 KB	Time limit exceeded (wall clock)
15	Execution timed out	22 ms	4064 KB	Time limit exceeded (wall clock)

Subtask #2

0 / 85.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	35 ms	5644 KB	Time limit exceeded (wall clock)
2	Execution timed out	38 ms	5320 KB	Time limit exceeded (wall clock)
3	Execution timed out	45 ms	7296 KB	Time limit exceeded (wall clock)
4	Execution timed out	27 ms	2524 KB	Time limit exceeded (wall clock)
5	Execution timed out	21 ms	3656 KB	Time limit exceeded (wall clock)
6	Execution timed out	39 ms	4012 KB	Time limit exceeded (wall clock)
7	Execution timed out	35 ms	5064 KB	Time limit exceeded (wall clock)
8	Execution timed out	52 ms	7704 KB	Time limit exceeded (wall clock)
9	Execution timed out	83 ms	10276 KB	Time limit exceeded (wall clock)
10	Execution timed out	83 ms	12016 KB	Time limit exceeded (wall clock)
11	Execution timed out	93 ms	10640 KB	Time limit exceeded (wall clock)
12	Execution timed out	89 ms	12744 KB	Time limit exceeded (wall clock)
13	Execution timed out	88 ms	12364 KB	Time limit exceeded (wall clock)
14	Execution timed out	136 ms	12388 KB	Time limit exceeded (wall clock)
15	Execution timed out	94 ms	13968 KB	Time limit exceeded (wall clock)
16	Execution timed out	96 ms	13944 KB	Time limit exceeded (wall clock)
17	Execution timed out	118 ms	13860 KB	Time limit exceeded (wall clock)