oj.uz

답안 #310583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310583 2020-10-07T12:42:32 Z shivensinha4 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 35400 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 = 2000;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 11520 KB Output is correct
2 Correct 10 ms 11648 KB Output is correct
3 Correct 12 ms 11520 KB Output is correct
4 Correct 14 ms 11520 KB Output is correct
5 Correct 17 ms 11520 KB Output is correct
6 Correct 29 ms 11768 KB Output is correct
7 Correct 37 ms 11648 KB Output is correct
8 Correct 30 ms 11732 KB Output is correct
9 Correct 58 ms 12464 KB Output is correct
10 Correct 88 ms 12280 KB Output is correct
11 Correct 138 ms 12664 KB Output is correct
12 Correct 149 ms 13332 KB Output is correct
13 Correct 190 ms 13048 KB Output is correct
14 Correct 257 ms 13872 KB Output is correct
15 Correct 283 ms 16248 KB Output is correct

Subtask #2
75.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1359 ms 17548 KB Output is correct
2 Correct 1604 ms 16284 KB Output is correct
3 Correct 2390 ms 20068 KB Output is correct
4 Correct 312 ms 14304 KB Output is correct
5 Correct 387 ms 16248 KB Output is correct
6 Correct 764 ms 15288 KB Output is correct
7 Correct 760 ms 16212 KB Output is correct
8 Correct 1351 ms 22904 KB Output is correct
9 Correct 2646 ms 25968 KB Output is correct
10 Correct 4624 ms 32224 KB Output is correct
11 Correct 4598 ms 26556 KB Output is correct
12 Correct 5662 ms 23744 KB Output is correct
13 Correct 6517 ms 24692 KB Output is correct
14 Execution timed out 8042 ms 25296 KB Time limit exceeded
15 Execution timed out 8044 ms 30692 KB Time limit exceeded
16 Correct 7896 ms 35400 KB Output is correct
17 Correct 7843 ms 34876 KB Output is correct