QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#773038 | #5439. Meet in the Middle | ucup-team3702 | WA | 118ms | 55176kb | C++14 | 6.3kb | 2024-11-23 00:03:14 | 2024-11-23 00:03:15 |
Judging History
answer
#include <map>
#include <set>
#include <list>
#include <array>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <memory>
#include <vector>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define per(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << " \n"[_ == r]
using i64 = long long;
const int N = 2e5 + 10;
const int Q = 5e5 + 10;
const int M = 20;
int read() {
int x = 0, f = 1; char c = getchar();
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + (c - 48);
return x * f;
}
int n, q, a[N], b[N];
i64 ans[Q];
vector <pair <int, int>> qry[N];
namespace t2 {
vector <pair <int, int>> e[N];
int p[N], sz[N], dfn[N], dn, st[M][N];
i64 dep[N];
void dfs0(int u, int fa) {
p[u] = fa, sz[u] = 1, dfn[u] = ++dn;
for (auto [v, w] : e[u]) if (v != fa) {
dep[v] = dep[u] + w, dfs0(v, u), sz[u] += sz[v];
}
}
int Min(int u, int v) {
return dep[u] < dep[v] ? u : v;
}
int lca(int u, int v) {
if (u == v) return u;
u = dfn[u], v = dfn[v];
if (u > v) swap(u, v);
int t = log2(v - u);
return p[Min(st[t][u + 1], st[t][v - (1 << t) + 1])];
}
i64 dis(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void init() {
rep(i, 1, n - 1) {
int u = read(), v = read(), w = read();
e[u].emplace_back(make_pair(v, w));
e[v].emplace_back(make_pair(u, w));
}
dfs0(1, 0);
rep(i, 1, n) st[0][dfn[i]] = i;
rep(j, 1, 19) rep(i, 1, n - (1 << j) + 1) {
st[j][i] = Min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
}
}
namespace t1 {
vector <pair <int, int>> e[N];
int dfn[N], dn, id[N], sz[N];
i64 dep[N];
void dfs0(int u, int fa) {
dfn[u] = ++dn, id[dn] = u, sz[u] = 1;
for (auto [v, w] : e[u]) if (v != fa) {
dep[v] = dep[u] + w, dfs0(v, u), sz[u] += sz[v];
}
}
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mid ((l + r) >> 1)
struct node {
int u, v;
i64 x, y, val;
node(int _u = 0, i64 _x = 0, int _v = 0, i64 _y = 0) {
u = _u, x = _x, v = _v, y = _y;
val = t2::dis(u, v) + x + y;
}
friend bool operator < (node p, node q) {
return p.val < q.val;
}
} dat[N << 2];
i64 laz[N << 2];
void down(int u, i64 k) {
dat[u].x += k, dat[u].y += k, dat[u].val += 2 * k;
laz[u] += k;
}
void pushdown(int u) {
if (laz[u]) {
down(ls, laz[u]), down(rs, laz[u]);
laz[u] = 0;
}
}
void maintain(int u) {
dat[u] = max(dat[ls], dat[rs]);
auto upd = [&](node res) {
if (dat[u] < res) dat[u] = res;
};
upd(node(dat[ls].u, dat[ls].x, dat[rs].u, dat[rs].x));
upd(node(dat[ls].u, dat[ls].x, dat[rs].v, dat[rs].y));
upd(node(dat[ls].v, dat[ls].y, dat[rs].u, dat[rs].x));
upd(node(dat[ls].v, dat[ls].y, dat[rs].v, dat[rs].y));
}
void build(int u, int l, int r) {
if (l == r) {
dat[u] = node(id[l], dep[id[l]], id[l], dep[id[l]]);
laz[u] = dep[id[l]];
return;
}
build(ls, l, mid);
build(rs, mid + 1, r);
maintain(u);
}
void modify(int ml, int mr, i64 k, int u, int l, int r) {
if (mr < l || r < ml) return;
if (ml <= l && r <= mr) {
down(u, k);
return;
}
pushdown(u);
modify(ml, mr, k, ls, l, mid);
modify(ml, mr, k, rs, mid + 1, r);
maintain(u);
}
i64 query(int p, int u, int l, int r) {
if (l == r) {
return laz[u];
}
pushdown(u);
i64 res = 0;
if (p <= mid) {
res = query(p, ls, l, mid);
res = max(res, node(id[p], 0, dat[rs].u, dat[rs].x).val);
res = max(res, node(id[p], 0, dat[rs].v, dat[rs].y).val);
} else {
res = query(p, rs, mid + 1, r);
res = max(res, node(id[p], 0, dat[ls].u, dat[ls].x).val);
res = max(res, node(id[p], 0, dat[ls].v, dat[ls].y).val);
// cout << dat[ls].u << ' ' << dat[ls].x << endl;
// cout << dat[ls].v << ' ' << dat[ls].y << endl;
}
// cout << "l, r, res = " << l << ' ' << r << ' ' << res << endl;
return res;
}
// void dfs(int u, int l, int r) {
// if (l == r) {
// cout << laz[u] << " \n"[r == n];
// return;
// }
// pushdown(u);
// dfs(ls, l, mid);
// dfs(rs, mid + 1, r);
// }
void dfs(int u, int l, int r) {
cout << "l, r, u, v = " << l << ' ' << r << ' ' << dat[u].u << ' ' << dat[u].v << endl;
if (l == r) return;
pushdown(u);
dfs(ls, l, mid);
dfs(rs, mid + 1, r);
maintain(u);
}
#undef ls
#undef rs
#undef mid
void init() {
rep(i, 1, n - 1) {
int u = read(), v = read(), w = read();
e[u].emplace_back(make_pair(v, w));
e[v].emplace_back(make_pair(u, w));
}
dfs0(1, 0);
}
void dfs1(int u, int fa) {
// pv(u);
// dfs(1, 1, n);
for (auto [v, id] : qry[u]) {
ans[id] = query(dfn[v], 1, 1, n);
}
for (auto [v, w] : e[u]) if (v != fa) {
modify(1, dfn[v] - 1, w, 1, 1, n);
modify(dfn[v], dfn[v] + sz[v] - 1, -w, 1, 1, n);
modify(dfn[v] + sz[v], n, w, 1, 1, n);
dfs1(v, u);
modify(1, dfn[v] - 1, -w, 1, 1, n);
modify(dfn[v], dfn[v] + sz[v] - 1, w, 1, 1, n);
modify(dfn[v] + sz[v], n, -w, 1, 1, n);
}
}
void work() {
// pa(id, 1, n);
rep(i, 1, q) {
int u = read(), v = read();
qry[u].emplace_back(make_pair(v, i));
}
build(1, 1, n);
dfs1(1, 0);
rep(i, 1, q) {
printf("%lld\n", ans[i]);
}
}
}
int main() {
n = read(), q = read();
t1::init();
t2::init();
// rep(u, 1, n) rep(v, 1, n) {
// cout << t2::dis(u, v) << " \n"[v == n];
// }
t1::work();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 55176kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
6 4 5 3
result:
ok 4 number(s): "6 4 5 3"
Test #2:
score: 0
Accepted
time: 7ms
memory: 50892kb
input:
2 1 1 2 1 1 2 1 1 1
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 3ms
memory: 55052kb
input:
2 1 1 2 1 1 2 1 1 2
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: -100
Wrong Answer
time: 118ms
memory: 48544kb
input:
10000 50000 8101 5996 108427744 5996 7605 870838849 5996 5599 603303696 8101 3006 339377417 8101 6463 442516687 6463 5560 109174079 5560 4063 127596224 3006 1682 947915262 5996 1986 130416311 6463 5455 279771516 6463 2634 516688796 4063 3034 217886863 7605 5092 742375061 5599 2266 193804402 5092 140...
output:
647838384844 626539793176 514273941704 637066393138 472546379596 645842915960 641537859258 573604504956 644081575470 803875451466 674370549986 734764046916 744862815441 763778393516 553499885160 526743824759 610373719514 689550247042 549161302822 726811438160 653134244120 666761991962 701575393972 6...
result:
wrong answer 298th numbers differ - expected: '586177604195', found: '585595903967'