QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127803 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | pandapythoner | 7 | 388ms | 101328kb | C++20 | 8.4kb | 2023-07-20 05:58:03 | 2023-07-20 05:58:05 |
Judging History
answer
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
mt19937 rnd(234);
const ll inf = 1e18;
struct Fenwick {
int n;
vector<int> t;
void build(int _n) {
n = _n;
t.assign(n + 1, 0);
}
void add(int i) {
i += 1;
if (i <= 0 || i > n) {
assert(0);
}
while (i <= n) {
t[i] += 1;
i = (i | (i - 1)) + 1;
}
}
int get(int r) {
r += 1;
if (r <= 0) {
return 0;
}
r = min(r, n);
int rs = 0;
while (r > 0) {
rs += t[r];
r = (r & (r - 1));
}
return rs;
}
};
struct ask {
int u, v;
int d;
};
struct bbr {
int d, f, i;
};
int n, q;
vector<vector<int>> g;
vector<ask> asks;
vector<int> sz;
vector<int> vmp;
vector<int> pr, ppr;
vector<int> dpth, dstx, dsty;
vector<vector<bbr>> b1, b2, b3, b4;
Fenwick f1, f2, f3;
vector<int> rs;
void dfs1(int v, int p) {
sz[v] = 1;
int mx_sz_i = -1;
int mx_sz = -1;
for (int i = 0; i < (int)g[v].size(); i += 1) {
int to = g[v][i];
if (to == p) {
continue;
}
dfs1(to, v);
sz[v] += sz[to];
if (sz[to] > mx_sz) {
mx_sz = sz[to];
mx_sz_i = i;
}
}
if (mx_sz_i != -1) {
swap(g[v][0], g[v][mx_sz_i]);
}
for (int i = 0; i < (int)g[v].size(); i += 1) {
int to = g[v][i];
if (to == p) {
g[v].erase(g[v].begin() + i);
break;
}
}
}
void dfs2(int v, int &c) {
vmp[v] = c;
c++;
for (auto to : g[v]) {
dfs2(to, c);
}
}
void hld_reorder() {
sz.resize(n);
dfs1(0, -1);
vmp.resize(n);
int c = 0;
dfs2(0, c);
vector<vector<int>> ng(n, vector<int>());
for (int v = 0; v < n; v += 1) {
for (auto to : g[v]) {
ng[vmp[v]].push_back(vmp[to]);
}
}
g.swap(ng);
for (auto &a : asks) {
a.u = vmp[a.u];
a.v = vmp[a.v];
}
}
void dfs3(int v, int p, int pp, int h, int y) {
dpth[v] = h;
pr[v] = p;
ppr[v] = pp;
dsty[v] = y;
dstx[v] = 0;
sz[v] = 1;
for (int i = 0; i < (int)g[v].size(); i += 1) {
int to = g[v][i];
if (i == 0) {
dfs3(to, v, pp, h + 1, y + 1);
dstx[v] = dstx[to] + 1;
} else {
dfs3(to, v, to, h + 1, 0);
}
sz[v] += sz[to];
}
}
void build() {
hld_reorder();
sz.resize(n);
pr.resize(n);
ppr.resize(n);
dpth.resize(n);
dstx.resize(n);
dsty.resize(n);
dfs3(0, -1, 0, 0, 0);
}
void dfs4(int v, int bnd, int h, int x) {
f1.add(h);
f2.add(h + x);
for (auto to : g[v]) {
if (to == bnd) {
continue;
}
dfs4(to, bnd, h + 1, x);
}
}
void dfs5(int v, int bnd, int h, int x) {
f3.add(h + x);
for (auto to : g[v]) {
if (to == bnd) {
continue;
}
dfs4(to, bnd, h + 1, x);
}
}
void solve_rec(int v) {
f1.build(sz[v]);
f2.build(sz[v]);
f3.build(sz[v]);
vector<int> way;
int u = v;
while (1) {
way.push_back(u);
int bnd = -1;
if (!g[u].empty()) {
bnd = g[u][0];
}
dfs4(u, bnd, 0, dstx[u]);
for (auto [d, f, i] : b1[u]) {
rs[i] += f * f1.get(d);
}
for (auto [d, f, i] : b2[u]) {
rs[i] += f * f2.get(d);
}
if (g[u].empty()) {
break;
}
u = g[u][0];
}
reverse(all(way));
for (auto u : way) {
int bnd = -1;
if (!g[u].empty()) {
bnd = g[u][0];
}
dfs5(u, bnd, 0, dsty[u]);
for (auto [d, f, i] : b3[u]) {
rs[i] += f * f3.get(d);
}
}
for (auto [d, f, i] : b4[v]) {
rs[i] += f * f3.get(d);
}
u = v;
while (1) {
for (int i = 1; i < (int)g[u].size(); i += 1) {
solve_rec(g[u][i]);
}
if (g[u].empty()) {
break;
}
u = g[u][0];
}
// g[n + 1].push_back(0);
}
void solve() {
rs.assign(q, 0);
build();
b1.assign(n, {});
b2.assign(n, {});
b3.assign(n, {});
b4.assign(n, {});
for (int i = 0; i < q; i += 1) {
auto a = asks[i];
auto [u, v, d] = a;
while (ppr[u] != ppr[v]) {
if (dpth[ppr[u]] > dpth[ppr[v]]) {
b1[u].push_back(bbr{d, 1, i});
if (!g[u].empty()) {
b3[g[u][0]].push_back(bbr{d + dsty[u], 1, i});
}
b4[ppr[u]].push_back(bbr{d - 1, -1, i});
u = pr[ppr[u]];
} else {
b1[v].push_back(bbr{d, 1, i});
if (!g[v].empty()) {
b3[g[v][0]].push_back(bbr{d + dsty[v], 1, i});
}
b4[ppr[v]].push_back(bbr{d - 1, -1, i});
v = pr[ppr[v]];
}
}
if (dpth[u] > dpth[v]) {
b1[u].push_back(bbr{d, 1, i});
if (!g[u].empty()) {
b3[g[u][0]].push_back(bbr{d + dsty[u], 1, i});
}
if (v != ppr[v]) {
b1[pr[v]].push_back(bbr{d, -1, i});
}
u = v;
} else {
b1[v].push_back(bbr{d, 1, i});
if (!g[v].empty()) {
b3[g[v][0]].push_back(bbr{d + dsty[v], 1, i});
}
if (u != ppr[u]) {
b1[pr[u]].push_back(bbr{d, -1, i});
}
v = u;
}
int dst = 1;
v = pr[v];
while (v != -1) {
if (dst > d) {
break;
}
b2[v].push_back(bbr{d + dstx[v] - dst, 1, i});
dst += (v - ppr[v] + 1);
b4[ppr[u]].push_back(bbr{d - dst - 1, -1, i});
v = pr[ppr[v]];
}
}
solve_rec(0);
}
void dfs_bebra(int v, int p, int h, vector<int> &d) {
d[v] = h;
for (auto to : g[v]) {
if (to == p) {
continue;
}
dfs_bebra(to, v, h + 1, d);
}
}
void solve_slow() {
hld_reorder();
for (int v = n - 1; v >= 0; v -= 1) {
for (auto to : g[v]) {
g[to].push_back(v);
}
}
rs.assign(q, 0);
vector<vector<int>> dsts(n, vector<int>(n));
for (int i = 0; i < n; i += 1) {
dfs_bebra(i, -1, 0, dsts[i]);
}
for (int i = 0; i < q; i += 1) {
auto [u, v, d] = asks[i];
for (int j = 0; j < n; j += 1) {
int dst = (dsts[u][j] + dsts[v][j] - dsts[u][v]) / 2;
if (dst <= d) {
rs[i] += 1;
}
}
}
}
void stress() {
int c = 0;
while (1) {
cout << ++c << "\n";
n = rnd() % 20 + 1;
vector<vector<int>> mg(n);
for (int v = 1; v < n; v += 1) {
int u = rnd() % v;
mg[u].push_back(v);
mg[v].push_back(u);
}
q = rnd() % 20 + 1;
vector<ask> masks(q);
for (int i = 0; i < q; i += 1) {
int u = rnd() % n;
int v = rnd() % n;
int d = rnd() % n;
masks[i] = ask{u, v, d};
}
g = mg;
asks = masks;
solve();
}
}
int32_t main() {
// stress();
if (1) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
cin >> n;
g.assign(n, vector<int>());
for (int i = 0; i < n - 1; i += 1) {
int u, v;
cin >> u >> v;
--u;
--v;
g[u].push_back(v);
g[v].push_back(u);
}
cin >> q;
asks.resize(q);
for (int i = 0; i < q; i += 1) {
int u, v, d;
cin >> u >> v >> d;
--u;
--v;
asks[i] = ask{u, v, d};
}
solve_slow();
for (int i = 0; i < q; i += 1) {
cout << rs[i] << "\n";
}
return 0;
}
/*
6
1 2
2 3
2 4
1 5
4 6
1
3 3 2
*/
详细
Subtask #1:
score: 7
Accepted
Test #1:
score: 7
Accepted
time: 366ms
memory: 101016kb
input:
4988 1 2 1 3 1 4 4 5 1 6 3 7 3 8 5 9 4 10 6 11 3 12 9 13 11 14 8 15 11 16 1 17 7 18 8 19 18 20 7 21 10 22 15 23 18 24 4 25 24 26 9 27 23 28 3 29 3 30 30 31 11 32 18 33 2 34 32 35 29 36 29 37 19 38 9 39 6 40 25 41 16 42 31 43 6 44 42 45 32 46 27 47 32 48 44 49 7 50 10 51 24 52 46 53 30 54 46 55 39 56...
output:
3226 2028 4988 208 252 3970 3886 2013 4974 2118 308 391 4768 312 4954 4988 4974 1551 4981 12 1856 4825 4974 4974 19 82 4960 4680 208 4870 474 3693 808 1880 213 3394 1203 266 84 4822 3334 70 81 4501 4960 668 4866 4974 113 490 75 163 209 2159 4981 4143 100 3168 232 66 4864 525 4958 390 4713 2305 15 49...
result:
ok 4966 numbers
Test #2:
score: 0
Accepted
time: 154ms
memory: 98156kb
input:
4914 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 54 27 ...
output:
3378 4914 231 4914 4914 3378 22 4914 4914 2559 4914 75 219 1407 1138 863 24 3890 4914 4914 399 399 13 139 77 4914 4095 3071 4914 23 151 110 1407 43 54 4914 4914 1919 2559 77 735 3071 24 133 479 4914 33 831 4 4914 4914 79 4914 199 3890 3071 73 567 15 75 21 126 4914 4914 203 4914 75 127 62 41 4914 409...
result:
ok 4975 numbers
Test #3:
score: 0
Accepted
time: 325ms
memory: 98340kb
input:
4921 1151 2767 2767 322 322 4451 4451 4867 4867 1265 1265 3197 3197 3890 3890 1052 1052 1407 1407 1578 1578 566 566 2965 2965 260 260 4908 4908 308 308 553 553 2845 2845 4249 4249 1284 1284 73 73 1088 1088 277 277 1878 1878 4128 4128 3609 3609 2126 2126 149 149 3467 3467 1653 1653 4913 4913 3604 360...
output:
4921 3192 3260 3983 949 2080 605 3471 4901 2020 2552 1570 3325 3643 458 1296 3072 3423 3045 2569 1720 3195 1908 4397 1536 2799 3072 2443 3176 3311 1403 1119 842 3028 2387 1903 2303 4921 2149 1974 4153 2053 2888 2344 3264 3709 3443 3601 2571 1207 4519 3745 959 1920 1305 1706 1743 522 1266 2153 1812 1...
result:
ok 4930 numbers
Test #4:
score: 0
Accepted
time: 282ms
memory: 99392kb
input:
4942 877 4180 4180 4409 4409 2233 2233 3491 3491 3459 3459 4501 4501 2192 2192 3539 3539 4379 4379 4346 4346 1553 1553 2100 2100 3426 3426 3461 3461 811 811 2981 2981 1493 1493 610 610 599 599 1741 1741 3216 3216 1646 1646 1016 1016 3757 3757 2570 2570 2900 2900 4649 4649 1014 1014 538 538 4288 4288...
output:
4236 3338 4942 4942 4942 4942 1551 1272 3885 4140 4942 3627 3132 3991 3157 4024 4942 4942 3761 3064 238 4942 4942 4942 4942 4942 2256 4942 649 4496 4942 4942 4491 866 4208 4942 4942 4726 4942 4462 4942 4942 4234 2676 2593 4942 4088 4942 2704 3344 3560 4942 4942 4461 4511 4634 3437 2884 3842 4942 494...
result:
ok 4910 numbers
Test #5:
score: 0
Accepted
time: 388ms
memory: 101328kb
input:
4996 1 2 2 3 1 4 4 5 4 6 3 7 4 8 8 9 3 10 9 11 5 12 7 13 12 14 8 15 8 16 14 17 10 18 15 19 17 20 15 21 19 22 21 23 14 24 20 25 25 26 21 27 20 28 19 29 29 30 24 31 31 32 29 33 27 34 34 35 31 36 27 37 30 38 35 39 38 40 37 41 34 42 41 43 43 44 42 45 36 46 37 47 47 48 47 49 41 50 50 51 46 52 50 53 51 54...
output:
4869 3419 3000 4640 4996 4996 3854 4165 4542 4996 1758 3584 3011 4996 4996 4383 2064 4199 2786 2470 4759 4996 4657 4157 2443 2594 1823 3215 1635 3908 1903 3207 2153 4448 4996 4996 3071 2649 3452 4996 1235 1599 2732 2244 2311 4618 1250 4577 3498 4941 1058 3498 3539 3415 907 4170 4996 4144 2235 2664 4...
result:
ok 4952 numbers
Test #6:
score: 0
Accepted
time: 179ms
memory: 99184kb
input:
4935 1 2 1 3 4 2 5 2 6 4 7 4 8 6 9 6 10 8 11 8 12 10 13 10 14 12 15 12 16 14 17 14 18 16 19 16 20 18 21 18 22 20 23 20 24 22 25 22 26 24 27 24 28 26 29 26 30 28 31 28 32 30 33 30 34 32 35 32 36 34 37 34 38 36 39 36 40 38 41 38 42 40 43 40 44 42 45 42 46 44 47 44 48 46 49 46 50 48 51 48 52 50 53 50 5...
output:
4442 4133 346 3268 4850 3512 3312 3581 4092 4655 2256 3950 3157 3480 4935 4188 4935 1593 1135 4935 4935 4875 4108 3771 4158 4935 4935 3156 3148 1814 4935 3368 4303 2861 4917 2370 3992 4764 2772 4935 4935 2640 4935 4691 2291 4268 1798 4530 3058 3219 4935 3141 4935 2699 4547 2164 2495 3049 370 3409 21...
result:
ok 4992 numbers
Test #7:
score: 0
Accepted
time: 193ms
memory: 98376kb
input:
4919 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
2653 3219 4302 1418 1713 713 3341 647 487 1508 971 4851 4443 3078 2380 2267 4171 18 2056 1833 3136 817 4375 4103 3423 433 3967 725 282 2358 4171 1680 3350 2403 802 1855 137 2091 3731 1061 581 1273 4783 133 1911 4239 4233 678 3127 3481 284 1896 435 593 4781 103 4647 1615 1231 2689 574 1833 4783 645 4...
result:
ok 4980 numbers
Test #8:
score: 0
Accepted
time: 376ms
memory: 100456kb
input:
4973 1 4517 2 744 3 1115 4 3191 5 4186 6 4608 7 3898 8 3939 9 1998 10 2287 11 2277 12 4200 13 4935 14 3955 15 3683 16 278 17 547 18 3351 19 2642 20 4050 21 3457 22 2337 23 3435 24 1476 25 4853 26 3985 27 736 28 3016 29 4840 30 3866 31 4567 32 4067 33 3724 34 1872 35 1533 36 4787 37 53 38 1632 39 295...
output:
91 2487 2646 1791 2447 3327 532 1801 1079 1526 1236 77 4028 3401 4103 1573 3540 1641 452 52 2497 3128 2593 734 1293 3213 1786 1626 2130 2033 1935 2673 1758 1838 1284 758 2952 301 947 2875 3073 1462 2615 2842 3561 1969 1416 3088 2476 1082 696 3665 2041 3263 3063 2988 1402 1050 2967 3696 2309 3767 281...
result:
ok 4982 numbers
Subtask #2:
score: 0
Memory Limit Exceeded
Test #9:
score: 0
Memory Limit Exceeded
input:
199995 1 2 2 3 2 4 1 5 3 6 5 7 6 8 4 9 2 10 5 11 5 12 1 13 1 14 1 15 13 16 1 17 10 18 16 19 11 20 8 21 17 22 4 23 19 24 7 25 22 26 8 27 14 28 1 29 9 30 3 31 3 32 21 33 19 34 26 35 34 36 5 37 29 38 22 39 5 40 13 41 28 42 8 43 35 44 22 45 14 46 12 47 32 48 11 49 8 50 18 51 23 52 18 53 4 54 6 55 10 56 ...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Memory Limit Exceeded
Test #25:
score: 0
Memory Limit Exceeded
input:
199991 1 2 2 3 3 4 3 5 5 6 3 7 1 8 8 9 8 10 10 11 1 12 1 13 13 14 4 15 12 16 13 17 17 18 8 19 3 20 9 21 16 22 10 23 1 24 7 25 6 26 12 27 4 28 21 29 27 30 30 31 21 32 19 33 20 34 17 35 7 36 13 37 24 38 37 39 30 40 31 41 15 42 9 43 32 44 41 45 18 46 38 47 8 48 35 49 13 50 35 51 47 52 35 53 48 54 44 55...
output:
result:
Subtask #5:
score: 0
Memory Limit Exceeded
Dependency #1:
100%
Accepted
Test #33:
score: 0
Memory Limit Exceeded
input:
49994 1 2 1 3 1 4 4 5 4 6 2 7 5 8 2 9 5 10 3 11 11 12 5 13 2 14 5 15 14 16 15 17 15 18 11 19 7 20 2 21 1 22 21 23 15 24 22 25 16 26 22 27 16 28 11 29 17 30 21 31 3 32 22 33 3 34 33 35 34 36 17 37 22 38 21 39 22 40 11 41 14 42 30 43 42 44 27 45 41 46 21 47 5 48 17 49 40 50 31 51 23 52 40 53 17 54 39 ...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%