QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#127792 | #5020. 举办乘凉州喵,举办乘凉州谢谢喵 | pandapythoner | 0 | 294ms | 61636kb | C++20 | 6.8kb | 2023-07-20 05:42:15 | 2023-07-20 05:42:18 |
Judging History
answer
#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];
}
}
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[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});
}
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);
}
int32_t main() {
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
Runtime Error
Test #1:
score: 0
Runtime Error
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:
result:
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 294ms
memory: 61636kb
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
Runtime Error
Test #25:
score: 0
Runtime Error
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
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%