#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int MAXN = 2e5;
const int MAXR = 25 * 1e3;
const int mod = 1572869;
int r[MAXN], timer, in[MAXN], out[MAXN];
vector<int> G[MAXN], R[MAXR], pos[MAXR];
vector<pair<int,int>> H[mod];
void dfs(int u) {
in[u] = ++timer;
pos[r[u]].emplace_back(in[u]);
for (int v : G[u])
dfs(v);
out[u] = timer;
}
void Insert(int x, int val) {
H[x % mod].emplace_back(x, val);
}
int Find(int x) {
int key = x % mod;
for (auto it : H[key])
if (it.first == x)
return it.second;
return -1;
}
int solve(int r1, int r2) {
int ans = 0;
for (int u : R[r1]) {
int st = lower_bound(pos[r2].begin(), pos[r2].end(), in[u]) - pos[r2].begin();
int dr = upper_bound(pos[r2].begin(), pos[r2].end(), out[u]) - pos[r2].begin();
ans += dr - st;
}
return ans;
}
int main() {
int n, Q;
cin >> n >> Q >> Q;
for (int v = 0; v < n; ++v) {
if (v == 0) {
cin >> r[0];
--r[0];
R[r[0]].emplace_back(0);
continue;
}
int u;
cin >> u >> r[v];
--r[v];
G[u - 1].emplace_back(v);
R[r[v]].emplace_back(v);
}
dfs(0);
for (int q = 0; q < Q; ++q) {
int r1, r2;
cin >> r1 >> r2;
--r1, --r2;
int h = r1 * MAXR + r2;
int ans = Find(h);
if (ans != -1)
cout << ans << endl;
else {
int ans = solve(r1, r2);
Insert(h, ans);
cout << ans << endl;
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
43136 KB |
Output is correct |
2 |
Correct |
28 ms |
43072 KB |
Output is correct |
3 |
Correct |
29 ms |
43120 KB |
Output is correct |
4 |
Correct |
32 ms |
43108 KB |
Output is correct |
5 |
Correct |
40 ms |
43148 KB |
Output is correct |
6 |
Correct |
63 ms |
43184 KB |
Output is correct |
7 |
Correct |
53 ms |
43220 KB |
Output is correct |
8 |
Correct |
78 ms |
43200 KB |
Output is correct |
9 |
Correct |
119 ms |
43700 KB |
Output is correct |
10 |
Correct |
94 ms |
43836 KB |
Output is correct |
11 |
Correct |
232 ms |
44180 KB |
Output is correct |
12 |
Correct |
201 ms |
44752 KB |
Output is correct |
13 |
Correct |
300 ms |
44660 KB |
Output is correct |
14 |
Correct |
324 ms |
45048 KB |
Output is correct |
15 |
Correct |
416 ms |
47012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1768 ms |
48276 KB |
Output is correct |
2 |
Correct |
1675 ms |
47496 KB |
Output is correct |
3 |
Correct |
2793 ms |
50940 KB |
Output is correct |
4 |
Correct |
421 ms |
45596 KB |
Output is correct |
5 |
Correct |
605 ms |
46948 KB |
Output is correct |
6 |
Correct |
887 ms |
46964 KB |
Output is correct |
7 |
Correct |
1076 ms |
47640 KB |
Output is correct |
8 |
Correct |
1754 ms |
52916 KB |
Output is correct |
9 |
Correct |
2641 ms |
56224 KB |
Output is correct |
10 |
Correct |
5432 ms |
60824 KB |
Output is correct |
11 |
Correct |
5365 ms |
57804 KB |
Output is correct |
12 |
Correct |
5688 ms |
56308 KB |
Output is correct |
13 |
Correct |
7108 ms |
57108 KB |
Output is correct |
14 |
Execution timed out |
8063 ms |
57116 KB |
Time limit exceeded |
15 |
Execution timed out |
8076 ms |
61316 KB |
Time limit exceeded |
16 |
Execution timed out |
8026 ms |
66184 KB |
Time limit exceeded |
17 |
Correct |
6800 ms |
65176 KB |
Output is correct |