#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
struct Queries {
int r1, r2;
Queries() {}
Queries(int _r1, int _r2): r1(_r1), r2(_r2) {}
};
const int N = 2e5 + 5;
const int R = 25 * 1e3 + 5;
Queries qr[N];
vector<int> id[R], reg[R], adj[N], e[R];
map<int, int> save[R];
map<int, bool> exist[R];
int l[N], r[N];
int cnt;
void dfs(int fa, int u) {
l[u] = ++cnt;
for (int v : adj[u])
if (v != fa)
dfs(u, v);
r[u] = cnt;
}
void solve() {
int n, regs, q;
cin >> n >> regs >> q;
int x;
cin >> x;
reg[x].push_back(1);
for (int i = 2; i <= n; i++) {
int p;
cin >> p;
adj[i].push_back(p);
adj[p].push_back(i);
int h;
cin >> h;
reg[h].push_back(i);
}
cnt = 0;
dfs(0, 1);
for (int i = 1; i <= regs; i++) {
for (int x : reg[i]) {
e[i].push_back(l[x]);
}
}
for (int i = 1; i <= regs; i++)
sort(e[i].begin(), e[i].end());
for (int i = 1; i <= q; i++) {
int r1, r2;
cin >> r1 >> r2;
if (exist[r1][r2]) {
cout << save[r1][r2] << endl;
}
else {
int ans = 0;
for (int x : reg[r1]) {
int u = lower_bound(e[r2].begin(), e[r2].end(), l[x]) - e[r2].begin();
int v = upper_bound(e[r2].begin(), e[r2].end(), r[x]) - e[r2].begin();
ans += 1ll * (v - u);
}
exist[r1][r2] = true;
save[r1][r2] = ans;
cout << ans << endl;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9060 KB |
Output is correct |
2 |
Correct |
5 ms |
9040 KB |
Output is correct |
3 |
Correct |
7 ms |
9040 KB |
Output is correct |
4 |
Correct |
7 ms |
9144 KB |
Output is correct |
5 |
Correct |
13 ms |
9208 KB |
Output is correct |
6 |
Correct |
26 ms |
9360 KB |
Output is correct |
7 |
Correct |
36 ms |
9444 KB |
Output is correct |
8 |
Correct |
41 ms |
9544 KB |
Output is correct |
9 |
Correct |
62 ms |
10044 KB |
Output is correct |
10 |
Correct |
71 ms |
10324 KB |
Output is correct |
11 |
Correct |
144 ms |
10832 KB |
Output is correct |
12 |
Correct |
171 ms |
11416 KB |
Output is correct |
13 |
Correct |
197 ms |
11592 KB |
Output is correct |
14 |
Correct |
218 ms |
11812 KB |
Output is correct |
15 |
Correct |
299 ms |
14424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1605 ms |
16092 KB |
Output is correct |
2 |
Correct |
1747 ms |
15792 KB |
Output is correct |
3 |
Correct |
2636 ms |
21288 KB |
Output is correct |
4 |
Correct |
244 ms |
13240 KB |
Output is correct |
5 |
Correct |
459 ms |
15692 KB |
Output is correct |
6 |
Correct |
632 ms |
15140 KB |
Output is correct |
7 |
Correct |
924 ms |
14960 KB |
Output is correct |
8 |
Correct |
1282 ms |
23748 KB |
Output is correct |
9 |
Correct |
2784 ms |
30708 KB |
Output is correct |
10 |
Correct |
5077 ms |
37860 KB |
Output is correct |
11 |
Correct |
4950 ms |
38260 KB |
Output is correct |
12 |
Correct |
5017 ms |
26752 KB |
Output is correct |
13 |
Correct |
5581 ms |
30644 KB |
Output is correct |
14 |
Correct |
7112 ms |
32964 KB |
Output is correct |
15 |
Correct |
7769 ms |
40548 KB |
Output is correct |
16 |
Correct |
5999 ms |
46628 KB |
Output is correct |
17 |
Correct |
5909 ms |
44764 KB |
Output is correct |