QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#80134 | #5439. Meet in the Middle | APJifengc | WA | 35ms | 55176kb | C++20 | 5.2kb | 2023-02-22 15:53:12 | 2023-02-22 15:53:16 |
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[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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 52768kb
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: 4ms
memory: 52828kb
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: 4ms
memory: 54796kb
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: 35ms
memory: 55176kb
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:
796729819588 648876407178 536610555706 785957827882 494882993598 794734350704 784510291018 595941118958 666418189472 826212065468 817342981746 757100660918 764355428210 783271006285 696472316920 669716256519 629866332283 832522678802 692133734582 749148052162 672626856889 689098605964 713654294175 8...
result:
wrong answer 1st numbers differ - expected: '647838384844', found: '796729819588'