QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#80135 | #5439. Meet in the Middle | APJifengc | WA | 39ms | 57060kb | C++20 | 5.2kb | 2023-02-22 15:54:19 | 2023-02-22 15:54:22 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int n, q;
struct Tree {
#define forGraph(u, v) for (int i = fst[u], v = to[i]; i; i = nxt[i], v = to[i])
int fst[MAXN], to[MAXN], nxt[MAXN], w[MAXN], tot;
void add(int u, int v, int ww) {
to[++tot] = v, nxt[tot] = fst[u], fst[u] = tot, w[tot] = ww;
}
};
struct Tree1 : public Tree {
int dfn[MAXN], idf[MAXN], dcnt;
int dep[MAXN];
int st[MAXN][20];
long long dis[MAXN];
void dfs(int u, int pre) {
dfn[u] = ++dcnt, idf[dcnt] = u;
dep[u] = dep[pre] + 1;
forGraph(u, v) if (v != pre) {
dis[v] = dis[u] + w[i];
dfs(v, u);
idf[++dcnt] = u;
}
}
void build() {
for (int i = 1; i <= dcnt; i++)
st[i][0] = idf[i];
for (int j = 1; j <= 18; j++) {
for (int i = 1; i + (1 << j) - 1 <= dcnt; i++) {
st[i][j] = (dep[st[i][j - 1]] < dep[st[i + (1 << (j - 1))][j - 1]]) ?
st[i][j - 1] : st[i + (1 << (j - 1))][j - 1];
}
}
}
int lca(int u, int v) {
int l = dfn[u], r = dfn[v];
if (l > r) swap(l, r);
int len = __lg(r - l + 1);
return dep[st[l][len]] < dep[st[r - (1 << len) + 1][len]] ?
st[l][len] : st[r - (1 << len) + 1][len];
}
long long dist(int u, int v) {
return dis[u] + dis[v] - 2 * dis[lca(u, v)];
}
} t1;
struct SegmentTree {
struct Chain {
pair<int, long long> u, v;
long long dist;
inline Chain() : u(), v(), dist(0) {}
inline Chain(pair<int, long long> u, pair<int, long long> v) : u(u), v(v) {
dist = t1.dist(u.first, v.first) + u.second + v.second;
}
inline bool operator<(const Chain &b) const {
return dist < b.dist;
}
inline Chain operator+(const Chain &b) const {
if (!u.first && !v.first) return b;
if (!b.u.first && !b.v.first) return *this;
Chain c = max(*this, b);
for (auto x : {u, v}) if (x.first) {
for (auto y : {b.u, b.v}) if (y.first) {
c = max(c, Chain(x, y));
}
}
return c;
}
};
struct Node {
Chain chain;
int tag;
} t[MAXN << 2];
#define lc (i << 1)
#define rc (i << 1 | 1)
void tag(int i, int v) {
t[i].tag += v;
t[i].chain.u.second += v;
t[i].chain.v.second += v;
t[i].chain.dist += 2 * v;
}
void pushDown(int i) {
if (t[i].tag) {
tag(lc, t[i].tag);
tag(rc, t[i].tag);
t[i].tag = 0;
}
}
void pushUp(int i) {
t[i].chain = t[lc].chain + t[rc].chain;
}
void build(int *idf, long long *dis, int i = 1, int l = 1, int r = n) {
if (l == r) {
t[i].chain.u.first = idf[l];
t[i].chain.u.second = dis[idf[l]];
return;
}
int mid = (l + r) >> 1;
build(idf, dis, lc, l, mid);
build(idf, dis, rc, mid + 1, r);
pushUp(i);
}
void add(int a, int b, int v, int i = 1, int l = 1, int r = n) {
if (a <= l && r <= b) {
tag(i, v);
return;
}
int mid = (l + r) >> 1;
pushDown(i);
if (a <= mid) add(a, b, v, lc, l, mid);
if (b > mid) add(a, b, v, rc, mid + 1, r);
pushUp(i);
}
} st;
long long ans[MAXN];
struct Tree2 : public Tree {
long long dis[MAXN];
int dfn[MAXN], ed[MAXN], idf[MAXN], dcnt;
void dfs1(int u, int pre) {
dfn[u] = ++dcnt, idf[dcnt] = u;
forGraph(u, v) if (v != pre) {
dis[v] = dis[u] + w[i];
dfs1(v, u);
}
ed[u] = dcnt;
}
void build() {
st.build(idf, dis);
}
vector<pair<int, int>> qs[MAXN];
void dfs2(int u, int pre) {
for (auto p : qs[u]) {
ans[p.first] = max(
t1.dist(st.t[1].chain.u.first, p.second) + st.t[1].chain.u.second,
t1.dist(st.t[1].chain.v.first, p.second) + st.t[1].chain.v.second
);
}
forGraph(u, v) if (v != pre) {
st.add(1, n, w[i]);
st.add(dfn[v], ed[v], -2 * w[i]);
dfs2(v, u);
st.add(1, n, -w[i]);
st.add(dfn[v], ed[v], 2 * w[i]);
}
}
} t2;
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);
t1.add(u, v, w);
t1.add(v, u, w);
}
t1.dfs(1, 0);
t1.build();
for (int i = 1; i < n; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
t2.add(u, v, w);
t2.add(v, u, w);
}
t2.dfs1(1, 0);
t2.build();
for (int i = 1; i <= q; i++) {
int a, b; scanf("%d%d", &a, &b);
t2.qs[b].push_back({i, a});
}
t2.dfs2(1, 0);
for (int i = 1; i <= q; i++) {
printf("%lld\n", ans[i]);
}
return 0;
}
/*
3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 52744kb
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: 5ms
memory: 57060kb
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: 5ms
memory: 52756kb
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: 39ms
memory: 56584kb
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:
756171780984 630834760472 518568909000 745399789278 452428534374 754176312100 801732359852 589153328707 648376542766 808170418762 834565050580 739059014212 749157782737 768073360812 713694385754 686938325353 631536005150 849744747636 709355803416 731106405456 657429211416 671056959258 701575393972 7...
result:
wrong answer 1st numbers differ - expected: '647838384844', found: '756171780984'