oj.uz

Submission #310360

# Submission time Handle Problem Language Result Execution time Memory
310360 2020-10-06T17:47:28 Z shivensinha4 Regions (IOI09_regions) C++17
90 / 100
 8000 ms 36500 KB 
#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;
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];
unordered_map<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;
	}
 
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7552 KB Output is correct
2 Correct 5 ms 7552 KB Output is correct
3 Correct 7 ms 7552 KB Output is correct
4 Correct 11 ms 7552 KB Output is correct
5 Correct 13 ms 7680 KB Output is correct
6 Correct 31 ms 7800 KB Output is correct
7 Correct 32 ms 7800 KB Output is correct
8 Correct 34 ms 7908 KB Output is correct
9 Correct 63 ms 8312 KB Output is correct
10 Correct 101 ms 8440 KB Output is correct
11 Correct 162 ms 8824 KB Output is correct
12 Correct 181 ms 9496 KB Output is correct
13 Correct 188 ms 9080 KB Output is correct
14 Correct 268 ms 9720 KB Output is correct
15 Correct 290 ms 12280 KB Output is correct

Subtask #2
75.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1717 ms 13432 KB Output is correct
2 Correct 1925 ms 12152 KB Output is correct
3 Correct 2971 ms 16912 KB Output is correct
4 Correct 281 ms 10392 KB Output is correct
5 Correct 452 ms 12412 KB Output is correct
6 Correct 593 ms 11988 KB Output is correct
7 Correct 730 ms 12832 KB Output is correct
8 Correct 1493 ms 19464 KB Output is correct
9 Correct 2882 ms 22956 KB Output is correct
10 Correct 5187 ms 28984 KB Output is correct
11 Correct 5608 ms 25076 KB Output is correct
12 Correct 5758 ms 21856 KB Output is correct
13 Correct 6553 ms 23472 KB Output is correct
14 Execution timed out 8010 ms 24368 KB Time limit exceeded
15 Execution timed out 8020 ms 29812 KB Time limit exceeded
16 Correct 7831 ms 36500 KB Output is correct
17 Correct 7088 ms 34752 KB Output is correct