#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"
const int RAD = 500;
const int MAX_N = 2e5;
int H[1 + MAX_N];
vector <int> gr[1 + MAX_N];
vector <int> order[1 + MAX_N];
vector <int> v[1 + MAX_N];
int L[1 + MAX_N], R[1 + MAX_N];
int id[1 + MAX_N];
int sol[RAD][1 + MAX_N];
int freq[1 + MAX_N];
void dfs(int node, int cnt, int color) {
if (H[node] == color)
cnt++;
else
sol[id[color]][H[node]] += cnt;
for (int son : gr[node])
dfs(son, cnt, color);
}
int mom;
void prec(int node) {
L[node] = ++mom;
order[H[node]].push_back(mom);
for (int son : gr[node])
prec(son);
R[node] = mom;
}
int get(int lb, int rb, int color) {
return upper_bound(order[color].begin(), order[color].end(), rb) - lower_bound(order[color].begin(), order[color].end(), lb);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int N, RR, Q;
cin >> N >> RR >> Q;
for (int i = 1; i <= N; i++) {
if (i == 1)
cin >> H[i];
else {
int par;
cin >> par >> H[i];
gr[par].push_back(i);
}
}
for (int i = 1; i <= N; i++) {
freq[H[i]]++;
v[H[i]].push_back(i);
}
int nr = 0;
for (int i = 1; i <= RR; i++) {
if (freq[i] > RAD) {
id[i] = ++nr;
dfs(1, 0, i);
}
}
prec(1);
while (Q--) {
int a, b;
cin >> a >> b;
if (freq[a] > RAD)
cout << sol[id[a]][b] << "\n";
else {
int ans = 0;
for (int node : v[a])
ans += get(L[node], R[node], b);
cout << ans << "\n";
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
6 ms |
14280 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
8 ms |
14408 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
7 ms |
14408 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
6 ms |
14408 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
7 ms |
14388 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
7 ms |
14396 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
7 ms |
14408 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
7 ms |
14408 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
8 ms |
14792 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
10 ms |
14920 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
14 ms |
15176 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
12 ms |
15548 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
12 ms |
15424 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
16 ms |
15956 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
17 ms |
17860 KB |
Time limit exceeded (wall clock) |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
40 ms |
19068 KB |
Time limit exceeded (wall clock) |
2 |
Execution timed out |
61 ms |
17884 KB |
Time limit exceeded (wall clock) |
3 |
Execution timed out |
45 ms |
20796 KB |
Time limit exceeded (wall clock) |
4 |
Execution timed out |
15 ms |
16072 KB |
Time limit exceeded (wall clock) |
5 |
Execution timed out |
19 ms |
17220 KB |
Time limit exceeded (wall clock) |
6 |
Execution timed out |
22 ms |
17220 KB |
Time limit exceeded (wall clock) |
7 |
Execution timed out |
32 ms |
18244 KB |
Time limit exceeded (wall clock) |
8 |
Execution timed out |
36 ms |
22204 KB |
Time limit exceeded (wall clock) |
9 |
Execution timed out |
55 ms |
23496 KB |
Time limit exceeded (wall clock) |
10 |
Execution timed out |
55 ms |
27456 KB |
Time limit exceeded (wall clock) |
11 |
Execution timed out |
71 ms |
23740 KB |
Time limit exceeded (wall clock) |
12 |
Execution timed out |
116 ms |
25252 KB |
Time limit exceeded (wall clock) |
13 |
Execution timed out |
114 ms |
25404 KB |
Time limit exceeded (wall clock) |
14 |
Execution timed out |
399 ms |
27004 KB |
Time limit exceeded (wall clock) |
15 |
Execution timed out |
112 ms |
29772 KB |
Time limit exceeded (wall clock) |
16 |
Execution timed out |
73 ms |
34988 KB |
Time limit exceeded (wall clock) |
17 |
Execution timed out |
127 ms |
35552 KB |
Time limit exceeded (wall clock) |