#include <bits/stdc++.h>
using namespace std;
const int N = (int) 2e5 + 7;
const int R = 25000 + 7;
const int CNT = 10;
int n;
int r;
int q;
int par[N];
int id[N];
int type[N];
vector<int> g[N];
vector<int> pos[R];
vector<int> verts[R];
int low[N];
int high[N];
int top;
int solution[CNT + 7][R];
void build(int a) {
low[a] = ++top;
verts[type[a]].push_back(a);
pos[type[a]].push_back(top);
for (auto &b : g[a]) {
build(b);
}
high[a] = top;
}
int getcnt(int prefix, int value) {
int sol = 0, low = 0, high = (int) pos[value].size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (pos[value][mid] <= prefix) {
sol = mid + 1;
low = mid + 1;
} else {
high = mid - 1;
}
}
return sol;
}
signed main() {
///freopen ("input", "r", stdin);
cin >> n >> r >> q;
cin >> type[1];
for (int i = 2; i <= n; i++) {
cin >> par[i] >> type[i];
g[par[i]].push_back(i);
}
build(1);
vector<pair<int, int>> ord;
for (int i = 1; i <= n; i++) {
ord.push_back({(int) verts[i].size(), i});
}
sort(ord.rbegin(), ord.rend());
int y = 0;
for (int j = 0; j < min(n, CNT); j++) {
int i = ord[j].second;
y++;
id[i] = y;
for (auto &v : verts[i]) {
for (int b = 1; b <= n; b++) {
solution[y][b] += getcnt(high[v], b) - getcnt(low[v] - 1, b);
}
}
}
for (int iq = 1; iq <= q; iq++) {
int a, b;
cin >> a >> b;
if (id[a]) {
cout << solution[id[a]][b] << "\n";
continue;
}
int sol = 0;
for (auto &v : verts[a]) {
sol += getcnt(high[v], b) - getcnt(low[v] - 1, b);
}
cout << sol << endl;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
6088 KB |
Output is correct |
2 |
Correct |
3 ms |
6216 KB |
Output is correct |
3 |
Correct |
5 ms |
6216 KB |
Output is correct |
4 |
Correct |
7 ms |
6216 KB |
Output is correct |
5 |
Correct |
12 ms |
6216 KB |
Output is correct |
6 |
Correct |
23 ms |
6348 KB |
Output is correct |
7 |
Correct |
39 ms |
6344 KB |
Output is correct |
8 |
Correct |
46 ms |
6344 KB |
Output is correct |
9 |
Correct |
49 ms |
7092 KB |
Output is correct |
10 |
Correct |
103 ms |
7312 KB |
Output is correct |
11 |
Correct |
154 ms |
7936 KB |
Output is correct |
12 |
Correct |
208 ms |
8656 KB |
Output is correct |
13 |
Correct |
255 ms |
8528 KB |
Output is correct |
14 |
Incorrect |
419 ms |
9304 KB |
Output isn't correct |
15 |
Incorrect |
521 ms |
11964 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
8022 ms |
12304 KB |
Time limit exceeded |
2 |
Execution timed out |
8052 ms |
11084 KB |
Time limit exceeded |
3 |
Execution timed out |
8090 ms |
14144 KB |
Time limit exceeded |
4 |
Incorrect |
554 ms |
9504 KB |
Output isn't correct |
5 |
Incorrect |
503 ms |
11016 KB |
Output isn't correct |
6 |
Correct |
3030 ms |
10972 KB |
Output is correct |
7 |
Incorrect |
3785 ms |
12372 KB |
Output isn't correct |
8 |
Incorrect |
3461 ms |
17792 KB |
Output isn't correct |
9 |
Incorrect |
5091 ms |
19060 KB |
Output isn't correct |
10 |
Execution timed out |
8020 ms |
24172 KB |
Time limit exceeded |
11 |
Execution timed out |
8055 ms |
19576 KB |
Time limit exceeded |
12 |
Execution timed out |
8005 ms |
19848 KB |
Time limit exceeded |
13 |
Execution timed out |
8022 ms |
20144 KB |
Time limit exceeded |
14 |
Execution timed out |
8015 ms |
20000 KB |
Time limit exceeded |
15 |
Execution timed out |
8005 ms |
24448 KB |
Time limit exceeded |
16 |
Execution timed out |
8029 ms |
29708 KB |
Time limit exceeded |
17 |
Execution timed out |
8052 ms |
28484 KB |
Time limit exceeded |