oj.uz

Submission #764110

# Submission time Handle Problem Language Result Execution time Memory
764110 2023-06-23T07:17:17 Z a_aguilo Regions (IOI09_regions) C++14
0 / 100
 136 ms 13968 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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)