/**
* author: wxhtzdy
* created: 16.07.2022 11:38:01
**/
#include <bits/stdc++.h>
using namespace std;
const int BLOCK = 1000;
const int MAX_T = 200005 / BLOCK;
const int MAX_R = 25005;
int U[MAX_T][MAX_R];
int D[MAX_T][MAX_R];
int cnt[MAX_R];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, r, q;
cin >> n >> r >> q;
vector<vector<int>> g(n);
vector<int> reg(n);
for (int i = 0; i < n; i++) {
if (i > 0) {
int p;
cin >> p;
--p;
g[p].push_back(i);
}
cin >> reg[i];
--reg[i];
}
vector<int> cc(r);
for (int i = 0; i < n; i++) {
cc[reg[i]] += 1;
}
vector<bool> h(r);
vector<int> id(r);
vector<int> xs;
int T = 0;
for (int i = 0; i < r; i++) {
if (cc[i] >= BLOCK) {
h[i] = true;
id[i] = ++T;
xs.push_back(i);
}
}
for (int i = 0; i <= T; i++) {
for (int j = 0; j < r; j++) {
U[i][j] = D[i][j] = 0;
}
}
vector<vector<pair<int, int>>> ev(r);
vector<vector<int>> my(r);
function<void(int)> Dfs = [&](int v) {
if (h[reg[v]]) {
for (int i = 0; i < r; i++) {
U[id[reg[v]]][i] += cnt[i];
}
}
for (int i : xs) {
D[id[i]][reg[v]] += cnt[i];
}
cnt[reg[v]] += 1;
++T;
ev[reg[v]].emplace_back(T - 1, -1);
my[reg[v]].push_back(T);
for (int u : g[v]) {
Dfs(u);
}
ev[reg[v]].emplace_back(T, +1);
cnt[reg[v]] -= 1;
};
Dfs(0);
while (q--) {
int r1, r2;
cin >> r1 >> r2;
--r1; --r2;
if (h[r1]) {
cout << D[id[r1]][r2] << endl;
} else if (h[r2]) {
cout << U[id[r2]][r1] << endl;
} else {
int ptr = 0;
long long ans = 0;
for (int i = 0; i < (int) ev[r1].size(); i++) {
while (ptr < (int) my[r2].size() && my[r2][ptr] <= ev[r1][i].first) {
ptr += 1;
}
ans += ptr * ev[r1][i].second;
}
cout << ans << endl;
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
208 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
2 ms |
336 KB |
Output is correct |
4 |
Correct |
4 ms |
336 KB |
Output is correct |
5 |
Correct |
11 ms |
336 KB |
Output is correct |
6 |
Correct |
10 ms |
464 KB |
Output is correct |
7 |
Correct |
12 ms |
464 KB |
Output is correct |
8 |
Correct |
23 ms |
464 KB |
Output is correct |
9 |
Correct |
47 ms |
1328 KB |
Output is correct |
10 |
Correct |
86 ms |
1232 KB |
Output is correct |
11 |
Correct |
129 ms |
1756 KB |
Output is correct |
12 |
Correct |
121 ms |
2600 KB |
Output is correct |
13 |
Correct |
169 ms |
2352 KB |
Output is correct |
14 |
Correct |
162 ms |
3204 KB |
Output is correct |
15 |
Correct |
219 ms |
8504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
718 ms |
8416 KB |
Output is correct |
2 |
Correct |
1002 ms |
6640 KB |
Output is correct |
3 |
Correct |
1320 ms |
11972 KB |
Output is correct |
4 |
Correct |
242 ms |
3408 KB |
Output is correct |
5 |
Correct |
331 ms |
6720 KB |
Output is correct |
6 |
Correct |
608 ms |
5596 KB |
Output is correct |
7 |
Correct |
859 ms |
7524 KB |
Output is correct |
8 |
Correct |
986 ms |
17156 KB |
Output is correct |
9 |
Correct |
1266 ms |
17296 KB |
Output is correct |
10 |
Correct |
1496 ms |
26840 KB |
Output is correct |
11 |
Correct |
2088 ms |
17904 KB |
Output is correct |
12 |
Correct |
4125 ms |
18424 KB |
Output is correct |
13 |
Correct |
4048 ms |
19652 KB |
Output is correct |
14 |
Correct |
7657 ms |
21160 KB |
Output is correct |
15 |
Correct |
6647 ms |
27924 KB |
Output is correct |
16 |
Correct |
6765 ms |
40404 KB |
Output is correct |
17 |
Correct |
7976 ms |
39808 KB |
Output is correct |