oj.uz

Submission #310361

# Submission time Handle Problem Language Result Execution time Memory
310361 2020-10-06T17:48:44 Z shivensinha4 Regions (IOI09_regions) C++17
100 / 100
 7776 ms 37464 KB 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#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];
gp_hash_table<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 9 ms 11520 KB Output is correct
2 Correct 10 ms 11520 KB Output is correct
3 Correct 12 ms 11520 KB Output is correct
4 Correct 16 ms 11520 KB Output is correct
5 Correct 16 ms 11520 KB Output is correct
6 Correct 26 ms 11648 KB Output is correct
7 Correct 36 ms 11692 KB Output is correct
8 Correct 45 ms 11844 KB Output is correct
9 Correct 46 ms 12272 KB Output is correct
10 Correct 108 ms 12280 KB Output is correct
11 Correct 129 ms 12664 KB Output is correct
12 Correct 119 ms 13336 KB Output is correct
13 Correct 178 ms 13088 KB Output is correct
14 Correct 300 ms 13616 KB Output is correct
15 Correct 319 ms 16248 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1414 ms 17400 KB Output is correct
2 Correct 1813 ms 16212 KB Output is correct
3 Correct 2864 ms 19860 KB Output is correct
4 Correct 336 ms 14144 KB Output is correct
5 Correct 473 ms 16092 KB Output is correct
6 Correct 517 ms 15408 KB Output is correct
7 Correct 1145 ms 16124 KB Output is correct
8 Correct 1387 ms 22956 KB Output is correct
9 Correct 2772 ms 25604 KB Output is correct
10 Correct 4929 ms 32064 KB Output is correct
11 Correct 4689 ms 26496 KB Output is correct
12 Correct 5635 ms 24460 KB Output is correct
13 Correct 6396 ms 25552 KB Output is correct
14 Correct 7660 ms 26128 KB Output is correct
15 Correct 7776 ms 31388 KB Output is correct
16 Correct 7072 ms 37464 KB Output is correct
17 Correct 6499 ms 36244 KB Output is correct