oj.uz

Submission #310357

# Submission time Handle Problem Language Result Execution time Memory
310357 2020-10-06T17:38:13 Z shivensinha4 Regions (IOI09_regions) C++17
60 / 100
 8000 ms 46924 KB 
#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;
int n, r, q;
int reg[MXN+1], tin[MXN+1], tout[MXN+1], pt = 0;
vi adj[MXN+1];
vector<vi> regList[MXR+1];
gp_hash_table<int, int> seen[MXR+1];
 
void dfs(int p, int parent) {
	regList[reg[p]].push_back({pt, 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;
		}
		//cout << r1 << " " << r2 << endl;
		int ans = 0;
		for (auto i: regList[r1]) {
			//cout << ptb-pta << endl;
			ans += upper_bound(regList[r2].begin(), regList[r2].end(), (vi) {tout[i[1]], INF})-lower_bound(regList[r2].begin(), regList[r2].end(), (vi) {tin[i[1]]+1, -1});
		}
		cout << ans << endl;
		seen[r1][r2] = ans;
	}
 
	return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 10880 KB Output is correct
2 Correct 9 ms 10880 KB Output is correct
3 Correct 11 ms 10880 KB Output is correct
4 Correct 14 ms 11008 KB Output is correct
5 Correct 17 ms 11008 KB Output is correct
6 Correct 28 ms 11128 KB Output is correct
7 Correct 31 ms 11200 KB Output is correct
8 Correct 60 ms 11256 KB Output is correct
9 Correct 71 ms 12096 KB Output is correct
10 Correct 119 ms 12408 KB Output is correct
11 Correct 201 ms 12948 KB Output is correct
12 Correct 288 ms 13896 KB Output is correct
13 Correct 370 ms 13876 KB Output is correct
14 Correct 655 ms 14656 KB Output is correct
15 Correct 774 ms 19348 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 3286 ms 21016 KB Output is correct
2 Correct 4117 ms 19568 KB Output is correct
3 Correct 5715 ms 24988 KB Output is correct
4 Correct 584 ms 15404 KB Output is correct
5 Correct 482 ms 18172 KB Output is correct
6 Correct 1081 ms 17400 KB Output is correct
7 Correct 1153 ms 18952 KB Output is correct
8 Correct 3609 ms 29260 KB Output is correct
9 Correct 7837 ms 33684 KB Output is correct
10 Execution timed out 8057 ms 38756 KB Time limit exceeded
11 Execution timed out 8050 ms 32580 KB Time limit exceeded
12 Execution timed out 8016 ms 31340 KB Time limit exceeded
13 Execution timed out 8080 ms 31976 KB Time limit exceeded
14 Execution timed out 8073 ms 32028 KB Time limit exceeded
15 Execution timed out 8048 ms 38128 KB Time limit exceeded
16 Execution timed out 8061 ms 46924 KB Time limit exceeded
17 Execution timed out 8068 ms 46024 KB Time limit exceeded