QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127799 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | pandapythoner | 0 | 499ms | 124460kb | C++20 | 7.5kb | 2023-07-20 05:49:58 | 2023-07-20 05:50:01 |
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);
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: 5952kb
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 1075 4971 12 1676 3619 5520 4783 19 82 5837 4084 203 5010 437 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 4400 508 4891 398 4060 1907 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: 284ms
memory: 61540kb
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:
628 61292 2752 97084 63604 155 23829 110186 5337 12222 9939 82871 209 499 15 8906 40 33015 165402 56 38488 107238 62473 2719 720 53 29282 44828 102921 139357 49829 85 1 6 4 3 3 11 48550 113400 102853 129396 119390 94280 46765 48352 175740 426 111715 144941 3359 26 82857 108038 115764 17205 5464 1281...
result:
wrong answer 1st numbers differ - expected: '757', found: '628'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 499ms
memory: 124460kb
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 107137 146159 5625 109830 196600 3767 90633 75 12997 149 58 707 209932 25 214767 491 216614 152523 9582 141771 184639 99 187595 70360 462 168847 126672 102926 282 191665 710 142 161509 2648 18643 131812 202928 2388 145457 181739 214113 13638 45356 71512 187518 114467 636 131 2108 220332 159872 19...
result:
wrong answer 2nd numbers differ - expected: '107329', found: '107137'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%