oj.uz

Submission #758103

# Submission time Handle Problem Language Result Execution time Memory
758103 2023-06-14T07:20:58 Z SanguineChameleon Regions (IOI09_regions) C++17
100 / 100
 5807 ms 36836 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const int maxn = 2e5 + 20;
const int maxk = 2.5e4 + 20;
int a[maxn];
vector<int> nodes[maxk];
vector<int> times[maxk];
vector<int> ch[maxn];
int tin[maxn];
int tout[maxn];
map<int, int> memo[maxk];
int n, k, q, t;

void dfs(int u) {
	tin[u] = ++t;
	nodes[a[u]].push_back(u);
	times[a[u]].push_back(tin[u]);
	for (auto v: ch[u]) {
		dfs(v);
	}
	tout[u] = t;
}

int query(int x, int y) {
	auto it = memo[x].find(y);
	if (it != memo[x].end()) {
		return it->second;
	}
	int res = 0;
	for (auto u: nodes[x]) {
		res += upper_bound(times[y].begin(), times[y].end(), tout[u]) - lower_bound(times[y].begin(), times[y].end(), tin[u]);
	}
	return (memo[x][y] = res);
}

void just_do_it() {
	cin >> n >> k >> q;
	cin >> a[1];
	for (int v = 2; v <= n; v++) {
		int u;
		cin >> u >> a[v];
		ch[u].push_back(v);
	}
	dfs(1);
	for (int i = 0; i < q; i++) {
		int x, y;
		cin >> x >> y;
		cout << query(x, y) << endl;
	}
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7376 KB Output is correct
2 Correct 7 ms 7380 KB Output is correct
3 Correct 5 ms 7376 KB Output is correct
4 Correct 10 ms 7396 KB Output is correct
5 Correct 11 ms 7432 KB Output is correct
6 Correct 25 ms 7524 KB Output is correct
7 Correct 32 ms 7524 KB Output is correct
8 Correct 40 ms 7528 KB Output is correct
9 Correct 54 ms 8072 KB Output is correct
10 Correct 82 ms 8232 KB Output is correct
11 Correct 101 ms 8608 KB Output is correct
12 Correct 146 ms 9140 KB Output is correct
13 Correct 155 ms 8896 KB Output is correct
14 Correct 214 ms 9532 KB Output is correct
15 Correct 189 ms 12404 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1247 ms 13280 KB Output is correct
2 Correct 1270 ms 12184 KB Output is correct
3 Correct 1623 ms 16832 KB Output is correct
4 Correct 243 ms 10236 KB Output is correct
5 Correct 291 ms 12208 KB Output is correct
6 Correct 575 ms 11824 KB Output is correct
7 Correct 871 ms 12252 KB Output is correct
8 Correct 1266 ms 19312 KB Output is correct
9 Correct 2265 ms 23096 KB Output is correct
10 Correct 3998 ms 29288 KB Output is correct
11 Correct 3856 ms 25352 KB Output is correct
12 Correct 3634 ms 21792 KB Output is correct
13 Correct 3996 ms 23672 KB Output is correct
14 Correct 5258 ms 24452 KB Output is correct
15 Correct 5807 ms 31056 KB Output is correct
16 Correct 5144 ms 36836 KB Output is correct
17 Correct 5161 ms 35140 KB Output is correct