Submission #310585

#	Time	Username	Problem	Language	Result	Execution time	Memory
310585		shivensinha4	Regions (IOI09_regions)	C++17	90 / 100	8020 ms	35684 KiB

regions

/*
 * 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 = 5000;
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 / 15
• Subtask 2: 75 / 85