oj.uz

Submission #310587

# Submission time Handle Problem Language Result Execution time Memory
310587 2020-10-07T12:47:23 Z shivensinha4 Regions (IOI09_regions) C++17
100 / 100
 7733 ms 37304 KB 
/*
 * Flatten the tree using Euler tour, note the end points of subtree of each node in tin[] and tout[].
 * Maintain the nodes in each region. Also keep a sorted list of tin[] of the nodes in each region.
 * For query (r1, r2), for each node 'i' in r1, binary search for the number of nodes in region r2 with tin[] between [tin[i]+1, tout[i]]. Add them all up to get the answer.
 * 
 * This works within the time limit because of the fact that there can only be a small amount of distinct regions queries (R * (R+1) / 2).
 * This means that there are a lot of repeated queries. Sadly, we cannot use a R*R array for keeping track of answers (MLE).
 * We use a gp_hash_table to keep track of the queries and their answers. If repeated, we just answer in constant time.
 * unordered_map usually missed one test case when I tried, so gets 95.
 * gp_hash_table gets 100.
 */
 
#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, k = 100000;
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;
		
		if (seen[r1].size() >= k) seen[r1].clear();
	}
 
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 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 15 ms 11520 KB Output is correct
5 Correct 18 ms 11520 KB Output is correct
6 Correct 28 ms 11768 KB Output is correct
7 Correct 39 ms 11648 KB Output is correct
8 Correct 46 ms 11856 KB Output is correct
9 Correct 57 ms 12152 KB Output is correct
10 Correct 82 ms 12408 KB Output is correct
11 Correct 131 ms 12792 KB Output is correct
12 Correct 149 ms 13304 KB Output is correct
13 Correct 186 ms 13048 KB Output is correct
14 Correct 258 ms 13688 KB Output is correct
15 Correct 282 ms 16248 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 17376 KB Output is correct
2 Correct 1573 ms 16016 KB Output is correct
3 Correct 2747 ms 19984 KB Output is correct
4 Correct 300 ms 14072 KB Output is correct
5 Correct 402 ms 16120 KB Output is correct
6 Correct 588 ms 15460 KB Output is correct
7 Correct 858 ms 16172 KB Output is correct
8 Correct 1243 ms 23048 KB Output is correct
9 Correct 2296 ms 25816 KB Output is correct
10 Correct 4620 ms 32216 KB Output is correct
11 Correct 4862 ms 26396 KB Output is correct
12 Correct 5275 ms 24528 KB Output is correct
13 Correct 6033 ms 25572 KB Output is correct
14 Correct 7733 ms 26352 KB Output is correct
15 Correct 7582 ms 31668 KB Output is correct
16 Correct 6881 ms 37304 KB Output is correct
17 Correct 6109 ms 36204 KB Output is correct