#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;
int n, r, q;
int R[200000];
vector<int> adj[200000];
vector<int> A[200001];
int start[200000], End[200000];
Tree<int> regions[200001];
int start2[200000], End2[200000];
vector<pair<int, int>> regions2[200001];
int regions2Ct[200001];
int ctr = 0;
void dfs(int u) {
start[u] = ctr;
for (int v : adj[u]) {
dfs(v);
}
End[u] = ctr++;
regions[R[u]].insert(End[u]);
}
int ctr2 = 0;
void dfs2(int u) {
start2[u] = ctr++;
regions2Ct[R[u]]++;
regions2[R[u]].push_back({start2[u], regions2Ct[R[u]]});
for (int v : adj[u]) {
dfs2(v);
}
regions2Ct[R[u]]--;
End2[u] = ctr;
regions2[R[u]].push_back({End2[u], regions2Ct[R[u]]});
}
int main() {
cin >> n >> r >> q;
for (int i = 0; i < n; i++) {
if (i == 0) {
cin >> R[i];
} else {
int p;
cin >> p >> R[i];
adj[p-1].push_back(i);
}
A[R[i]].push_back(i);
regions2Ct[R[i]] = 0;
}
dfs(0);
dfs2(0);
map<pair<int, int>, long long> cache;
for (int i = 0; i < q; i++) {
int a, b; cin >> a >> b;
if (cache.count(make_pair(a, b))) {
cout << cache[make_pair(a, b)] << endl;
continue;
}
bool swapped = false;
if (A[a].size() > A[b].size()) {
swap(a, b);
swapped = true;
}
long long ans = 0;
for (int n : A[a]) {
if (!swapped) {
int x = start[n], y = End[n];
ans += regions[b].order_of_key(y) - regions[b].order_of_key(x);
} else {
auto it = lower_bound(regions2[b].begin(), regions2[b].end(), make_pair(start2[n], -1));
if (it == regions2[b].begin()) continue;
ans += (--it)->second;
}
}
cout << ans << endl;
if (swapped) swap(a, b);
cache[make_pair(a, b)] = ans;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
26 ms |
30080 KB |
Output isn't correct |
2 |
Incorrect |
27 ms |
30080 KB |
Output isn't correct |
3 |
Incorrect |
28 ms |
30072 KB |
Output isn't correct |
4 |
Incorrect |
31 ms |
30080 KB |
Output isn't correct |
5 |
Incorrect |
34 ms |
30208 KB |
Output isn't correct |
6 |
Correct |
44 ms |
30336 KB |
Output is correct |
7 |
Incorrect |
47 ms |
30428 KB |
Output isn't correct |
8 |
Incorrect |
61 ms |
30584 KB |
Output isn't correct |
9 |
Correct |
83 ms |
31352 KB |
Output is correct |
10 |
Incorrect |
94 ms |
31868 KB |
Output isn't correct |
11 |
Incorrect |
221 ms |
32504 KB |
Output isn't correct |
12 |
Incorrect |
212 ms |
33656 KB |
Output isn't correct |
13 |
Incorrect |
259 ms |
33632 KB |
Output isn't correct |
14 |
Incorrect |
469 ms |
34680 KB |
Output isn't correct |
15 |
Correct |
483 ms |
38264 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1645 ms |
41504 KB |
Output isn't correct |
2 |
Incorrect |
1891 ms |
41064 KB |
Output isn't correct |
3 |
Incorrect |
3224 ms |
46876 KB |
Output isn't correct |
4 |
Incorrect |
377 ms |
35448 KB |
Output isn't correct |
5 |
Incorrect |
618 ms |
38176 KB |
Output isn't correct |
6 |
Incorrect |
761 ms |
38732 KB |
Output isn't correct |
7 |
Incorrect |
1083 ms |
40376 KB |
Output isn't correct |
8 |
Incorrect |
1534 ms |
50040 KB |
Output isn't correct |
9 |
Incorrect |
3662 ms |
58864 KB |
Output isn't correct |
10 |
Incorrect |
6319 ms |
66156 KB |
Output isn't correct |
11 |
Incorrect |
7095 ms |
65664 KB |
Output isn't correct |
12 |
Incorrect |
2717 ms |
59124 KB |
Output isn't correct |
13 |
Incorrect |
3428 ms |
61312 KB |
Output isn't correct |
14 |
Incorrect |
4228 ms |
63340 KB |
Output isn't correct |
15 |
Incorrect |
5478 ms |
70356 KB |
Output isn't correct |
16 |
Incorrect |
5781 ms |
75960 KB |
Output isn't correct |
17 |
Incorrect |
5610 ms |
74608 KB |
Output isn't correct |