oj.uz

답안 #310584

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
310584 2020-10-07T12:43:28 Z shivensinha4 Regions (IOI09_regions) C++17
85 / 100
 8000 ms 35468 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 = 1000;
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 12 ms 11520 KB Output is correct
3 Correct 12 ms 11520 KB Output is correct
4 Correct 12 ms 11564 KB Output is correct
5 Correct 16 ms 11596 KB Output is correct
6 Correct 31 ms 11648 KB Output is correct
7 Correct 40 ms 11648 KB Output is correct
8 Correct 47 ms 11768 KB Output is correct
9 Correct 71 ms 12280 KB Output is correct
10 Correct 102 ms 12256 KB Output is correct
11 Correct 137 ms 12664 KB Output is correct
12 Correct 207 ms 13180 KB Output is correct
13 Correct 178 ms 13024 KB Output is correct
14 Correct 281 ms 13560 KB Output is correct
15 Correct 344 ms 16296 KB Output is correct

Subtask #2
70.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1543 ms 17416 KB Output is correct
2 Correct 1855 ms 16116 KB Output is correct
3 Correct 2777 ms 19868 KB Output is correct
4 Correct 416 ms 14092 KB Output is correct
5 Correct 413 ms 16140 KB Output is correct
6 Correct 678 ms 15448 KB Output is correct
7 Correct 1000 ms 15944 KB Output is correct
8 Correct 1547 ms 22832 KB Output is correct
9 Correct 2892 ms 25692 KB Output is correct
10 Correct 5643 ms 32068 KB Output is correct
11 Correct 4919 ms 26480 KB Output is correct
12 Correct 5862 ms 23824 KB Output is correct
13 Correct 6466 ms 24724 KB Output is correct
14 Execution timed out 8055 ms 25040 KB Time limit exceeded
15 Execution timed out 8079 ms 30668 KB Time limit exceeded
16 Execution timed out 8022 ms 35468 KB Time limit exceeded
17 Correct 7539 ms 35324 KB Output is correct