oj.uz

Submission #310585

# Submission time Handle Problem Language Result Execution time Memory
310585 2020-10-07T12:43:40 Z shivensinha4 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 35684 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 = 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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11520 KB Output is correct
2 Correct 12 ms 11520 KB Output is correct
3 Correct 13 ms 11520 KB Output is correct
4 Correct 18 ms 11520 KB Output is correct
5 Correct 20 ms 11520 KB Output is correct
6 Correct 35 ms 11648 KB Output is correct
7 Correct 61 ms 11648 KB Output is correct
8 Correct 52 ms 11768 KB Output is correct
9 Correct 78 ms 12152 KB Output is correct
10 Correct 101 ms 12320 KB Output is correct
11 Correct 159 ms 12676 KB Output is correct
12 Correct 163 ms 13176 KB Output is correct
13 Correct 226 ms 13084 KB Output is correct
14 Correct 259 ms 13592 KB Output is correct
15 Correct 357 ms 16364 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1570 ms 17192 KB Output is correct
2 Correct 1878 ms 16124 KB Output is correct
3 Correct 2649 ms 19888 KB Output is correct
4 Correct 347 ms 14100 KB Output is correct
5 Correct 420 ms 16244 KB Output is correct
6 Correct 781 ms 15420 KB Output is correct
7 Correct 995 ms 16056 KB Output is correct
8 Correct 1468 ms 23008 KB Output is correct
9 Correct 3011 ms 25848 KB Output is correct
10 Correct 5249 ms 32120 KB Output is correct
11 Correct 5352 ms 26344 KB Output is correct
12 Correct 6033 ms 23852 KB Output is correct
13 Correct 6804 ms 24908 KB Output is correct
14 Execution timed out 8005 ms 25596 KB Time limit exceeded
15 Execution timed out 8020 ms 30988 KB Time limit exceeded
16 Correct 7283 ms 35684 KB Output is correct
17 Correct 6880 ms 35340 KB Output is correct