#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], -1));
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], -1));
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 |
3 ms |
344 KB |
Output isn't correct |
| 5 |
Incorrect |
4 ms |
344 KB |
Output isn't correct |
| 6 |
Incorrect |
13 ms |
600 KB |
Output isn't correct |
| 7 |
Incorrect |
17 ms |
344 KB |
Output isn't correct |
| 8 |
Incorrect |
13 ms |
600 KB |
Output isn't correct |
| 9 |
Incorrect |
25 ms |
1368 KB |
Output isn't correct |
| 10 |
Incorrect |
46 ms |
1112 KB |
Output isn't correct |
| 11 |
Incorrect |
77 ms |
1624 KB |
Output isn't correct |
| 12 |
Incorrect |
88 ms |
2648 KB |
Output isn't correct |
| 13 |
Incorrect |
122 ms |
2136 KB |
Output isn't correct |
| 14 |
Incorrect |
194 ms |
3036 KB |
Output isn't correct |
| 15 |
Incorrect |
130 ms |
8280 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1097 ms |
8060 KB |
Output isn't correct |
| 2 |
Incorrect |
1314 ms |
6232 KB |
Output isn't correct |
| 3 |
Incorrect |
1610 ms |
11544 KB |
Output isn't correct |
| 4 |
Incorrect |
189 ms |
3408 KB |
Output isn't correct |
| 5 |
Incorrect |
258 ms |
6644 KB |
Output isn't correct |
| 6 |
Incorrect |
388 ms |
8708 KB |
Output isn't correct |
| 7 |
Incorrect |
784 ms |
11112 KB |
Output isn't correct |
| 8 |
Incorrect |
777 ms |
24608 KB |
Output isn't correct |
| 9 |
Incorrect |
1601 ms |
16300 KB |
Output isn't correct |
| 10 |
Incorrect |
1824 ms |
45828 KB |
Output isn't correct |
| 11 |
Incorrect |
2925 ms |
16896 KB |
Output isn't correct |
| 12 |
Incorrect |
943 ms |
17632 KB |
Output isn't correct |
| 13 |
Incorrect |
1272 ms |
18808 KB |
Output isn't correct |
| 14 |
Incorrect |
1513 ms |
21520 KB |
Output isn't correct |
| 15 |
Incorrect |
2009 ms |
26960 KB |
Output isn't correct |
| 16 |
Incorrect |
1615 ms |
39616 KB |
Output isn't correct |
| 17 |
Incorrect |
1719 ms |
40056 KB |
Output isn't correct |
