oj.uz

Submission #310358

# Submission time Handle Problem Language Result Execution time Memory
310358 2020-10-06T17:43:14 Z shivensinha4 Regions (IOI09_regions) C++17
100 / 100
 7970 ms 37412 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 11 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 13 ms 11576 KB Output is correct
5 Correct 15 ms 11592 KB Output is correct
6 Correct 24 ms 11700 KB Output is correct
7 Correct 47 ms 11648 KB Output is correct
8 Correct 54 ms 11768 KB Output is correct
9 Correct 49 ms 12272 KB Output is correct
10 Correct 111 ms 12408 KB Output is correct
11 Correct 141 ms 12836 KB Output is correct
12 Correct 145 ms 13228 KB Output is correct
13 Correct 182 ms 13092 KB Output is correct
14 Correct 270 ms 13748 KB Output is correct
15 Correct 259 ms 16472 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1501 ms 17484 KB Output is correct
2 Correct 1581 ms 16324 KB Output is correct
3 Correct 2429 ms 19868 KB Output is correct
4 Correct 296 ms 14176 KB Output is correct
5 Correct 315 ms 16276 KB Output is correct
6 Correct 482 ms 15444 KB Output is correct
7 Correct 947 ms 16164 KB Output is correct
8 Correct 1386 ms 23012 KB Output is correct
9 Correct 2410 ms 25884 KB Output is correct
10 Correct 4509 ms 32300 KB Output is correct
11 Correct 4639 ms 26548 KB Output is correct
12 Correct 5524 ms 24508 KB Output is correct
13 Correct 6091 ms 25396 KB Output is correct
14 Correct 7302 ms 26140 KB Output is correct
15 Correct 7970 ms 31384 KB Output is correct
16 Correct 7163 ms 37412 KB Output is correct
17 Correct 6487 ms 35980 KB Output is correct