oj.uz

Submission #310586

# Submission time Handle Problem Language Result Execution time Memory
310586 2020-10-07T12:45:43 Z shivensinha4 Regions (IOI09_regions) C++17
100 / 100
 7926 ms 37196 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 = 20000;
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 17 ms 11520 KB Output is correct
6 Correct 28 ms 11648 KB Output is correct
7 Correct 37 ms 11648 KB Output is correct
8 Correct 45 ms 11856 KB Output is correct
9 Correct 57 ms 12152 KB Output is correct
10 Correct 90 ms 12324 KB Output is correct
11 Correct 129 ms 12664 KB Output is correct
12 Correct 145 ms 13260 KB Output is correct
13 Correct 177 ms 13048 KB Output is correct
14 Correct 275 ms 13820 KB Output is correct
15 Correct 281 ms 16248 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1392 ms 17244 KB Output is correct
2 Correct 1570 ms 16012 KB Output is correct
3 Correct 2238 ms 19980 KB Output is correct
4 Correct 280 ms 14200 KB Output is correct
5 Correct 384 ms 16128 KB Output is correct
6 Correct 609 ms 15388 KB Output is correct
7 Correct 775 ms 16136 KB Output is correct
8 Correct 1217 ms 23180 KB Output is correct
9 Correct 2365 ms 25848 KB Output is correct
10 Correct 4880 ms 32100 KB Output is correct
11 Correct 4946 ms 26520 KB Output is correct
12 Correct 5288 ms 24816 KB Output is correct
13 Correct 6152 ms 25328 KB Output is correct
14 Correct 7802 ms 26272 KB Output is correct
15 Correct 7926 ms 31492 KB Output is correct
16 Correct 6930 ms 37196 KB Output is correct
17 Correct 6529 ms 36148 KB Output is correct