QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#334161 | #6111. Two Paths | FISHER_ | WA | 165ms | 29216kb | C++14 | 4.6kb | 2024-02-21 11:55:29 | 2024-02-21 11:55:29 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
#define PB push_back
#define EB emplace_back
using namespace std;
typedef long long i64;
const int maxn = 200000;
int n, q;
struct edge { int v, w; };
vector<edge> g[maxn + 5];
int dep[maxn + 5];
pair<int, int> mx[maxn + 5], smx[maxn + 5], tmx[maxn + 5];
int siz[maxn + 5], son[maxn + 5];
void dfs(int u, int fa) {
siz[u] = 1;
for (const auto& [v, w] : g[u])
if (v != fa) {
dep[v] = dep[u] + w;
dfs(v, u);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
pair<int, int> nw = {mx[v].fi + w, v};
if (nw > mx[u]) tmx[u] = smx[u], smx[u] = mx[u], mx[u] = nw;
else if (nw > smx[u]) tmx[u] = smx[u], smx[u] = nw;
else tmx[u] = max(tmx[u], nw);
}
}
int tp[maxn + 5], f[maxn + 5];
int id[maxn + 5], rnk[maxn + 5], stamp;
void dfs2(int u, int fa, int t) {
tp[u] = t, f[u] = fa;
rnk[id[u] = ++stamp] = u;
if (son[u]) dfs2(son[u], u, t);
for (const auto& [v, _] : g[u])
if (v != fa && v != son[u]) dfs2(v, u, v);
}
int mxl[maxn + 5];
void dfs3(int u, int fa) {
for (const auto& [v, w] : g[u])
if (v != fa) {
mxl[v] = max(mxl[u], mx[u].se == v ? smx[u].fi : mx[u].fi) + w;
dfs3(v, u);
}
}
struct point {
i64 x, y;
bool operator<(const point& b) const { return x == b.x ? y > b.y : x < b.x; }
point operator-(const point& b) const { return {x - b.x, y - b.y}; }
i64 operator*(const point& b) const { return x * b.y - y * b.x; }
};
i64 mxa[4 * maxn + 5], mxb[4 * maxn + 5];
vector<point> h[4 * maxn + 5];
void build(int p, int l, int r) {
if (l == r) {
int u = rnk[l];
int mxd = mx[u].se == son[u] ? smx[u].fi : mx[u].fi;
mxa[p] = mxd - dep[u], mxb[p] = mxd + dep[u];
return;
}
int mid = (l + r) / 2;
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
vector<point> L = h[p << 1];
L.insert(L.end(), h[p << 1 | 1].begin(), h[p << 1 | 1].end());
L.PB({mxa[p << 1 | 1], mxb[p << 1]});
sort(L.begin(), L.end());
for (const auto& o : L) {
while (h[p].size() > 1 && (*(h[p].end() - 1) - *(h[p].end() - 2)) * (o - *(h[p].end() - 2)) >= 0) h[p].pop_back();
h[p].PB(o);
}
mxa[p] = max(mxa[p << 1], mxa[p << 1 | 1]), mxb[p] = max(mxb[p << 1], mxb[p << 1 | 1]);
}
i64 ans;
int A, B;
i64 pa;
int ea, eb;
inline void upd(i64 na, i64 nb) {
ans = max(ans, (pa + ea) * A + (nb + eb) * B);
pa = max(pa, na);
}
void query(int p, int l, int r, int x, int y) {
if (x <= l && r <= y) {
upd(mxa[p], mxb[p]);
if (h[p].empty()) return;
int L = 0, R = h[p].size() - 1;
while (L < R) {
int mid = (L + R + 1) / 2;
if (A * h[p][mid].x + B * h[p][mid].y > A * h[p][mid - 1].x + B * h[p][mid - 1].y) L = mid;
else R = mid - 1;
}
ans = max(ans, A * (h[p][L].x + ea) + B * (h[p][L].y + eb));
return;
}
int mid = (l + r) / 2;
if (mid < y) query(p << 1 | 1, mid + 1, r, x, y);
if (mid >= x) query(p << 1, l, mid, x, y);
}
void solve(int u, int v) {
vector<pair<int, int>> su, sv;
int tu = u, tv = v;
while (tp[tu] != tp[tv]) {
if (dep[tp[tu]] > dep[tp[tv]]) su.EB(id[tp[tu]], id[tu]), tu = f[tp[tu]];
else sv.EB(id[tp[tv]], id[tv]), tv = f[tp[tv]];
}
int z = tu;
if (tu != tv) {
if (dep[tu] > dep[tv]) su.EB(id[tv] + 1, id[tu]), z = tv;
else sv.EB(id[tu] + 1, id[tv]), z = tu;
}
pa = -2E9;
ea = dep[u], eb = dep[v] - 2 * dep[z];
int lst = 0;
for (const auto& [l, r] : su) {
int x = rnk[r];
int mxd = mx[x].se == lst ? smx[x].se : mx[x].se;
i64 na = mxd - dep[x], nb = mxd + dep[x];
upd(na, nb);
if (l < r) query(1, 1, n, l, r - 1);
lst = rnk[l];
}
i64 al = pa + ea; int la = lst;
pa = -2E9;
ea = dep[v], eb = dep[u] - 2 * dep[z];
lst = 0;
swap(A, B);
for (const auto& [l, r] : sv) {
int x = rnk[r];
int mxd = mx[x].se == lst ? smx[x].fi : mx[x].fi;
i64 na = mxd - dep[x], nb = mxd + dep[x];
upd(na, nb);
if (l < r) query(1, 1, n, l, r - 1);
lst = rnk[l];
}
i64 bl = pa + ea; int lb = lst;
swap(A, B);
ans = max(ans, al * A + bl * B);
int mxd = mx[z].se == la || mx[z].se == lb ? (smx[z].se == la || smx[z].se == lb ? tmx[z].fi : smx[z].fi) : mx[z].fi;
if (u != z) ans = max(ans, al * A + max(dep[z] + mxd, mxl[z] + dep[v] - dep[z]) * B);
if (v != z) ans = max(ans, max(dep[z] + mxd, mxl[z] + dep[u] - dep[z]) * A + bl * B);
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].PB({v, w}), g[v].PB({u, w});
}
dfs(1, 0), dfs2(1, 0, 1), dfs3(1, 0);
build(1, 1, n);
for (int i = 1; i <= q; i++) {
int u, v;
scanf("%d%d%d%d", &u, &v, &A, &B);
ans = 0, solve(u, v);
printf("%lld\n", ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 28876kb
input:
6 4 1 2 4 2 5 5 2 3 7 3 6 5 3 4 4 1 4 1 1 1 4 2 1 5 6 1 1 5 6 1 10
output:
18 32 18 160
result:
ok 4 number(s): "18 32 18 160"
Test #2:
score: 0
Accepted
time: 0ms
memory: 27908kb
input:
2 1 1 2 1 1 2 1 1
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 29216kb
input:
2 10 1 2 2 1 2 1 1 1 2 1 2 1 2 1 3 1 2 2 1 1 2 2 2 1 2 3 1 1 2 3 2 1 2 3 3 1 2 2 3 1 2 1 3
output:
0 0 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #4:
score: -100
Wrong Answer
time: 165ms
memory: 28912kb
input:
10 500000 4 5 576 5 8 218 1 10 678 1 9 2540 7 8 2023 2 7 5510 2 9 8454 4 6 22 3 9 5248 2 5 35782 82142 1 2 95412 85188 4 5 82466 22193 3 6 22169 67901 4 10 67229 30987 1 10 68282 17858 1 8 53726 3246 5 8 13913 74110 2 8 30052 7204 1 4 95255 48216 2 5 41392 98997 3 8 8435 5947 1 5 22067 21610 7 9 343...
output:
674365186 1454303268 476601225 1359445921 1501996827 1320778726 889342640 1573781502 426346196 1792561801 789005461 166905972 478560756 75994082 334573104 901237204 420263788 1710700661 367767940 307415352 1840589883 1679904905 1054831274 1644275016 79164180 602184744 873340490 815015664 1356022267 ...
result:
wrong answer 3rd numbers differ - expected: '477920681', found: '476601225'