#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#include "bits/stdc++.h"
using namespace std;
using LL = long long;
static constexpr int SQ = 256;
struct Segtree {
int n;
vector<int> t;
Segtree(int n) : n(n), t(2*n) {}
void update(int p, int v) {
for (t[p += n] += v; p > 1; p >>= 1) {
t[p >> 1] = t[p] + t[p ^ 1];
}
}
int query(int l, int r) {
int ans = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans += t[l++];
if (r & 1) ans += t[--r];
}
return ans;
}
};
int main() {
int n; cin >> n;
int r; cin >> r;
int q; cin >> q;
vector<int> h(n), p(n), f(r);
vector<vector<int>> adj(n);
cin >> h[0]; ++f[--h[0]];
for (int i = 1; i < n; ++i) {
cin >> p[i] >> h[i];
--p[i], --h[i];
adj[p[i]].push_back(i);
++f[h[i]];
}
vector<int> ff;
vector<int> fi(r, -1);
for (int i = 0; i < r; ++i) {
if (f[i] >= SQ) {
fi[i] = ff.size();
ff.push_back(i);
}
}
int nn = ff.size();
vector<int> in(n), out(n), ord;
{ // linearize the tree
int t = 0;
auto dfs = [&](auto&& self, int v) -> void {
in[v] = t++;
ord.push_back(v);
for (int u : adj[v]) {
self(self, u);
}
out[v] = t;
};
dfs(dfs, 0);
}
vector<vector<int>> vs(r);
{
for (int v : ord) {
int c = h[v];
vs[h[v]].push_back(v);
}
}
vector<vector<LL>> sub(r, vector<LL>(nn));
vector<vector<LL>> anc(r, vector<LL>(nn));
{
auto dfs = [&](auto&& self, int v, int i, int acc = 0) -> int {
int cnt = 0;
for (int u : adj[v]) {
cnt += self(self, u, i, acc + (h[v] == ff[i]));
}
sub[h[v]][i] += cnt;
anc[h[v]][i] += acc;
return cnt + (h[v] == ff[i]);
};
for (int i = 0; i < nn; ++i) {
dfs(dfs, 0, i);
}
}
Segtree st(n);
for (int r1, r2; q--;) {
cin >> r1 >> r2;
--r1, --r2;
if (f[r2] >= SQ) {
cout << sub[r1][fi[r2]] << endl;
} else if (f[r1] >= SQ) {
cout << anc[r2][fi[r2]] << endl;
} else {
LL ans = 0;
for (int v : vs[r2]) {
st.update(in[v], 1);
}
for (int u : vs[r1]) {
ans += st.query(in[u]+1, out[u]);
}
for (int v : vs[r2]) {
st.update(in[v], -1);
}
cout << ans << endl;
}
}
}
Compilation message
regions.cpp: In function 'int main()':
regions.cpp:68:17: warning: unused variable 'c' [-Wunused-variable]
68 | int c = h[v];
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
208 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
2 ms |
208 KB |
Output is correct |
4 |
Correct |
4 ms |
208 KB |
Output is correct |
5 |
Correct |
7 ms |
336 KB |
Output is correct |
6 |
Correct |
19 ms |
336 KB |
Output is correct |
7 |
Correct |
32 ms |
336 KB |
Output is correct |
8 |
Correct |
32 ms |
464 KB |
Output is correct |
9 |
Correct |
68 ms |
848 KB |
Output is correct |
10 |
Correct |
107 ms |
1232 KB |
Output is correct |
11 |
Correct |
146 ms |
1616 KB |
Output is correct |
12 |
Correct |
215 ms |
2180 KB |
Output is correct |
13 |
Correct |
230 ms |
2120 KB |
Output is correct |
14 |
Correct |
387 ms |
2884 KB |
Output is correct |
15 |
Correct |
608 ms |
5028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1498 ms |
7452 KB |
Output isn't correct |
2 |
Incorrect |
1484 ms |
6760 KB |
Output isn't correct |
3 |
Incorrect |
4606 ms |
9636 KB |
Output isn't correct |
4 |
Correct |
282 ms |
3240 KB |
Output is correct |
5 |
Correct |
599 ms |
4712 KB |
Output is correct |
6 |
Incorrect |
759 ms |
12220 KB |
Output isn't correct |
7 |
Incorrect |
1220 ms |
15396 KB |
Output isn't correct |
8 |
Incorrect |
1402 ms |
28800 KB |
Output isn't correct |
9 |
Incorrect |
3997 ms |
39428 KB |
Output isn't correct |
10 |
Incorrect |
3795 ms |
61272 KB |
Output isn't correct |
11 |
Runtime error |
186 ms |
131072 KB |
Execution killed with signal 9 |
12 |
Incorrect |
2253 ms |
19420 KB |
Output isn't correct |
13 |
Incorrect |
3082 ms |
19532 KB |
Output isn't correct |
14 |
Incorrect |
3417 ms |
26436 KB |
Output isn't correct |
15 |
Incorrect |
6136 ms |
24672 KB |
Output isn't correct |
16 |
Incorrect |
6505 ms |
29512 KB |
Output isn't correct |
17 |
Incorrect |
5525 ms |
34076 KB |
Output isn't correct |