oj.uz

Submission #764173

# Submission time Handle Problem Language Result Execution time Memory
764173 2023-06-23T08:15:07 Z a_aguilo Regions (IOI09_regions) C++14
6 / 100
 8000 ms 48452 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;
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]){
			int l = enter[i] + 1;
			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]--;
	}
	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:43:7: warning: unused variable 'B' [-Wunused-variable]
   43 |   int B = i/SQRT;
      |       ^

Subtask #1
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 4 ms 336 KB Output is correct
5 Correct 8 ms 336 KB Output is correct
6 Correct 20 ms 336 KB Output is correct
7 Incorrect 33 ms 472 KB Output isn't correct
8 Incorrect 35 ms 528 KB Output isn't correct
9 Incorrect 147 ms 1084 KB Output isn't correct
10 Incorrect 91 ms 1460 KB Output isn't correct
11 Incorrect 230 ms 2012 KB Output isn't correct
12 Incorrect 660 ms 3004 KB Output isn't correct
13 Incorrect 157 ms 2576 KB Output isn't correct
14 Incorrect 456 ms 3144 KB Output isn't correct
15 Incorrect 5780 ms 6292 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8005 ms 7992 KB Time limit exceeded
2 Execution timed out 8037 ms 7436 KB Time limit exceeded
3 Execution timed out 8090 ms 11128 KB Time limit exceeded
4 Runtime error 16 ms 4688 KB Execution killed with signal 11
5 Runtime error 24 ms 8368 KB Execution killed with signal 11
6 Runtime error 28 ms 8284 KB Execution killed with signal 11
7 Runtime error 37 ms 10608 KB Execution killed with signal 11
8 Runtime error 72 ms 21584 KB Execution killed with signal 11
9 Runtime error 86 ms 23596 KB Execution killed with signal 11
10 Runtime error 107 ms 34472 KB Execution killed with signal 11
11 Runtime error 108 ms 25244 KB Execution killed with signal 11
12 Runtime error 115 ms 28456 KB Execution killed with signal 11
13 Runtime error 106 ms 28812 KB Execution killed with signal 11
14 Runtime error 114 ms 28408 KB Execution killed with signal 11
15 Runtime error 115 ms 36936 KB Execution killed with signal 11
16 Runtime error 122 ms 48452 KB Execution killed with signal 11
17 Runtime error 122 ms 45628 KB Execution killed with signal 11