QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127800 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | pandapythoner | 0 | 558ms | 125188kb | C++20 | 7.6kb | 2023-07-20 05:52:03 | 2023-07-20 05:52:07 |
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 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();
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: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 8ms
memory: 6012kb
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:
2882 2147 5912 200 256 3979 3634 2060 5491 1597 306 342 4925 313 3636 3893 5207 1071 4971 12 1676 3619 5520 4771 19 82 5837 4084 203 5000 436 2932 649 1690 202 3497 1168 274 84 3330 3272 70 81 4286 5493 643 4793 5102 113 482 75 160 207 2202 5308 4485 100 2706 238 66 4390 508 4891 398 4060 1902 15 51...
result:
wrong answer 1st numbers differ - expected: '3226', found: '2882'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 344ms
memory: 74952kb
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:
611 61282 2742 97072 63565 154 23813 110168 5332 12217 9935 82851 200 496 14 8874 40 32990 165393 52 38480 107232 62443 2715 715 53 29276 44825 102911 139351 49821 78 1 6 4 3 3 10 48545 113394 102823 129378 119370 94276 46760 48346 175736 425 111700 144938 3335 26 82832 108018 115752 17193 5446 1273...
result:
wrong answer 1st numbers differ - expected: '757', found: '611'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 558ms
memory: 125188kb
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:
78 107128 146159 5625 109830 196582 3762 90633 75 12997 149 58 707 209932 25 214767 491 216614 152523 9582 141771 184624 99 187595 70352 462 168814 126659 102926 282 191665 710 142 161509 2648 18634 131812 202928 2388 145457 181739 214113 13634 45356 71505 187518 114458 636 131 2108 220332 159872 19...
result:
wrong answer 2nd numbers differ - expected: '107329', found: '107128'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%