oj.uz

Submission #310359

# Submission time Handle Problem Language Result Execution time Memory
310359 2020-10-06T17:45:25 Z shivensinha4 Regions (IOI09_regions) C++17
95 / 100
 8000 ms 36568 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'
 
const int MXN = 200000, MXR = 25000, INF = 1e9+1;
int n, r, q;
int reg[MXN+1], tin[MXN+1], tout[MXN+1], pt = 0;
vi adj[MXN+1];
vi regList[MXR+1], regListId[MXR+1];
unordered_map<int, int> seen[MXR+1];
 
void dfs(int p, int parent) {
	regList[reg[p]].push_back(pt);
	regListId[reg[p]].push_back(p);
	tin[p] = pt++;
	for (int i: adj[p]) if (i != parent) dfs(i, p);
	tout[p] = pt-1;
}
 
int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> r >> q;
	cin >> reg[0];
	reg[0] -= 1;
	
	for_(i, 1, n) {
		int p; cin >> p >> reg[i];
		reg[i] -= 1;
		adj[p-1].push_back(i);
	}
	
	dfs(0, 0);
	
	while (q--) {
		int r1, r2; cin >> r1 >> r2;
		r1 -= 1; r2 -= 1;
		if (seen[r1].find(r2) != seen[r1].end()) {
			cout << seen[r1][r2] << endl;
			continue;
		}
		int ans = 0;
		for (auto i: regListId[r1]) {
			ans += upper_bound(regList[r2].begin(), regList[r2].end(), tout[i]) - lower_bound(regList[r2].begin(), regList[r2].end(), tin[i]+1);
		}
		cout << ans << endl;
		seen[r1][r2] = ans;
	}
 
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7552 KB Output is correct
2 Correct 5 ms 7552 KB Output is correct
3 Correct 8 ms 7552 KB Output is correct
4 Correct 8 ms 7552 KB Output is correct
5 Correct 15 ms 7680 KB Output is correct
6 Correct 15 ms 7788 KB Output is correct
7 Correct 45 ms 7800 KB Output is correct
8 Correct 38 ms 7808 KB Output is correct
9 Correct 48 ms 8312 KB Output is correct
10 Correct 83 ms 8452 KB Output is correct
11 Correct 132 ms 8824 KB Output is correct
12 Correct 177 ms 9340 KB Output is correct
13 Correct 170 ms 9180 KB Output is correct
14 Correct 281 ms 9736 KB Output is correct
15 Correct 219 ms 12452 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1637 ms 13340 KB Output is correct
2 Correct 1423 ms 12300 KB Output is correct
3 Correct 2471 ms 16976 KB Output is correct
4 Correct 225 ms 10548 KB Output is correct
5 Correct 378 ms 12412 KB Output is correct
6 Correct 543 ms 12084 KB Output is correct
7 Correct 915 ms 12612 KB Output is correct
8 Correct 1437 ms 19708 KB Output is correct
9 Correct 2648 ms 22960 KB Output is correct
10 Correct 4710 ms 29056 KB Output is correct
11 Correct 4796 ms 25040 KB Output is correct
12 Correct 5358 ms 21992 KB Output is correct
13 Correct 6452 ms 23584 KB Output is correct
14 Correct 7848 ms 24596 KB Output is correct
15 Execution timed out 8082 ms 30908 KB Time limit exceeded
16 Correct 7430 ms 36568 KB Output is correct
17 Correct 6478 ms 35028 KB Output is correct