#include <bits/stdc++.h>
#define ll long long
using namespace std;
int cnt = 0, N, SQRT, R;
vector<int> a, in, out, occ;
vector<vector<int>> child;
map<int, vector<ll>> col;
map<int,int> curr;
vector<vector<pair<int,int>>> pref;
void dfs(int x) {
int last = 0;
if (!pref[a[x]].empty()) last = pref[a[x]].back().second;
pref[a[x]].push_back({cnt, last + 1});
in[x] = cnt++;
if (occ[a[x]] > SQRT) curr[a[x]]++;
for (int y : child[x]) {
dfs(y);
}
if (occ[a[x]] > SQRT) curr[a[x]] --;
for (auto z : curr) col[z.first][a[x]] += z.second;
out[x] = cnt;
}
signed main() {
ios::sync_with_stdio(false);
int Q; cin >> N >> R >> Q;
a.resize(N); child.resize(N); in.resize(N); out.resize(N); cin >> a[0]; a[0]--;
occ.resize(R, 0); occ[a[0]]++; pref.resize(R);
for (int i = 1; i < N; i++) {
int b; cin >> b >> a[i]; b--; a[i]--; occ[a[i]]++;
child[b].push_back(i);
}
SQRT=sqrt(N);
vector<vector<int>> temp(R);
for (int i = 0; i < N; i++) {
if (occ[a[i]] <= SQRT) temp[a[i]].push_back(i);
}
for (int i = 0; i < R; i++) {
if (occ[i] > SQRT) col[i].resize(R);
}
dfs(0);
while (Q--) {
int r1, r2; cin >> r1 >> r2; r1--; r2--;
if (occ[r1] > SQRT) cout << col[r1][r2] << '\n';
else {
ll ans = 0;
for (int x : temp[r1]) {
auto it = upper_bound(pref[r2].begin(), pref[r2].end(), make_pair(out[x], 0));
if (it == pref[r2].begin()) continue;
it--;
if ((*it).second < in[x]) continue;
int last = 0;
auto it2 = upper_bound(pref[r2].begin(), pref[r2].end(), make_pair(in[x], 0));
if (it2 != pref[r2].begin()) {
it2--;
last = (*it2).second;
}
ans += (*it).second - last;
}
cout << ans << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
344 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
344 KB |
Output isn't correct |
| 6 |
Incorrect |
9 ms |
600 KB |
Output isn't correct |
| 7 |
Incorrect |
14 ms |
600 KB |
Output isn't correct |
| 8 |
Incorrect |
15 ms |
600 KB |
Output isn't correct |
| 9 |
Incorrect |
19 ms |
1368 KB |
Output isn't correct |
| 10 |
Incorrect |
52 ms |
1112 KB |
Output isn't correct |
| 11 |
Incorrect |
67 ms |
1624 KB |
Output isn't correct |
| 12 |
Incorrect |
84 ms |
2648 KB |
Output isn't correct |
| 13 |
Incorrect |
125 ms |
2132 KB |
Output isn't correct |
| 14 |
Incorrect |
176 ms |
3032 KB |
Output isn't correct |
| 15 |
Incorrect |
143 ms |
8360 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1047 ms |
8056 KB |
Output isn't correct |
| 2 |
Incorrect |
1351 ms |
6244 KB |
Output isn't correct |
| 3 |
Incorrect |
1594 ms |
11540 KB |
Output isn't correct |
| 4 |
Incorrect |
175 ms |
3368 KB |
Output isn't correct |
| 5 |
Incorrect |
214 ms |
6648 KB |
Output isn't correct |
| 6 |
Incorrect |
408 ms |
8712 KB |
Output isn't correct |
| 7 |
Incorrect |
759 ms |
11124 KB |
Output isn't correct |
| 8 |
Incorrect |
779 ms |
24604 KB |
Output isn't correct |
| 9 |
Incorrect |
1609 ms |
16300 KB |
Output isn't correct |
| 10 |
Incorrect |
1898 ms |
45832 KB |
Output isn't correct |
| 11 |
Incorrect |
2951 ms |
16900 KB |
Output isn't correct |
| 12 |
Incorrect |
992 ms |
17624 KB |
Output isn't correct |
| 13 |
Incorrect |
1248 ms |
18812 KB |
Output isn't correct |
| 14 |
Incorrect |
1595 ms |
21516 KB |
Output isn't correct |
| 15 |
Incorrect |
2053 ms |
26828 KB |
Output isn't correct |
| 16 |
Incorrect |
1600 ms |
39612 KB |
Output isn't correct |
| 17 |
Incorrect |
1699 ms |
40056 KB |
Output isn't correct |
