QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139791 | #5439. Meet in the Middle | xcyle | WA | 90ms | 18228kb | C++20 | 4.0kb | 2023-08-14 16:44:13 | 2023-08-14 16:44:16 |
Judging History
answer
/*
_/ _/ _/_/_/ _/ _/ _/ _/_/_/_/_/
_/ _/ _/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/
_/_/ _/ _/ _/ _/_/_/_/
_/ _/ _/ _/ _/ _/
_/ _/ _/ _/ _/ _/ _/
_/ _/ _/_/_/ _/ _/_/_/_/_/ _/_/_/_/_/
*/
#include <bits/stdc++.h>
#define ll long long
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ru(i, l, r) for (int i = (l); i <= (r); i++)
#define rd(i, r, l) for (int i = (r); i >= (l); i--)
#define mid ((l + r) >> 1)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define sz(s) (int)s.size()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define maxn 100005
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
int read() {
int x = 0, w = 0; char ch = getchar();
while(!isdigit(ch)) w |= ch == '-', ch = getchar();
while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
return w ? -x : x;
}
int n, q, fa[maxn][22], tdep[maxn];
ll dep[maxn];
vector<pii> G[2][maxn];
void init(int x) {
ru(i, 1, 20) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for (auto [V, W]: G[1][x]) if(V ^ fa[x][0]) {
dep[V] = dep[x] + W, tdep[V] = tdep[x] + 1, fa[V][0] = x, init(V);
}
}
int dfn[maxn], tot, out[maxn], id[maxn];
ll t[maxn];
void add(int x, ll v) {
for (; x <= n; x += x & (-x)) t[x] += v;
}
ll que(int x) {
ll res = 0;
for (; x; x -= x & (-x)) res += t[x];
return res;
}
int lca(int x, int y) {
if(tdep[x] > tdep[y]) swap(x, y);
rd(i, 20, 0) if(tdep[fa[y][i]] >= tdep[x]) y = fa[y][i];
if(x == y) return x;
rd(i, 20, 0) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
ll dis(int x, int y) {
return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
vector<pii> ask[maxn];
ll ans[maxn];
struct diam {
int x, y;
}d[maxn];
void pushup(int o) {
int a[4] = {d[lc(o)].x, d[lc(o)].y, d[rc(o)].x, d[rc(o)].y};
int x = 0, y = 0; ll z = -1;
ru(i, 0, 3) ru(j, i + 1, 3) if(a[i] != a[j] && a[i] && a[j]) {
ll d = dis(id[a[i]], id[a[j]]) + que(a[i]) + que(a[j]);
//printf("! %d %d %d %d %d %d %lld %lld\n", a[i], a[j], que(a[i]), que(a[j]), id[a[i]], id[a[j]], dis(id[a[i]], id[a[j]]), d);
if(d > z) z = d, x = a[i], y = a[j];
}
d[o] = {x, y};
}
void upd(int x, int l, int r, int a, int b) {
if(a <= l && r <= b) {
if(!d[x].x) d[x] = {l, l};
return;
}
if(a <= mid) upd(lc(x), l, mid, a, b);
if(b > mid) upd(rc(x), mid + 1, r, a, b);
//printf("ee %d %d\n", l, r);
pushup(x);
}
void dfs1(int x, int fa, ll d) {
id[dfn[x] = ++tot] = x;
add(dfn[x], d), add(dfn[x] + 1, -d);
upd(1, 1, n, dfn[x], dfn[x]);
for (auto [V, W]: G[0][x]) if(V ^ fa) dfs1(V, x, d + W);
out[x] = tot;
}
void dfs2(int x, int fa) {
//printf("? %d\n", x);
int a = id[d[1].x], b = id[d[1].y]; //printf("! %d %d %d\n", x, a, b);
for (auto [v, id]: ask[x]) {
ans[id] = max(que(a) + dis(v, a), que(b) + dis(v, b));
}
for (auto [V, W]: G[0][x]) if(V ^ fa) {
add(1, W), add(dfn[x], -2 * W), add(out[x] + 1, W);
dfs2(V, x);
add(1, -W), add(dfn[x], 2 * W), add(out[x] + 1, -W);
}
}
int main() {
n = read(), q = read();
ru(j, 0, 1) {
ru(i, 1, n - 1) {
int u = read(), v = read(), w = read();
G[j][u].push_back(mp(v, w)), G[j][v].push_back(mp(u, w));
}
}
ru(i, 1, q) {
int u = read(), v = read();
ask[u].push_back(mp(v, i));
}
init(1);
dfs1(1, 0, 0);
dfs2(1, 0);
ru(i, 1, q) printf("%lld\n", ans[i]);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 13920kb
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: 3ms
memory: 13904kb
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: 13924kb
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: 90ms
memory: 18228kb
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:
348880919079 409640328896 298416415722 315847101269 255183024384 313571361896 299016076511 357746978974 428154834114 443833978942 358264017474 476921526052 336252239285 257681829659 281276412547 216021712321 247624285993 335853784380 237168931652 435325271650 308664245551 447604450091 313981266261 3...
result:
wrong answer 1st numbers differ - expected: '647838384844', found: '348880919079'