QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#87489 | #5439. Meet in the Middle | Acestar | WA | 52ms | 37900kb | C++14 | 3.4kb | 2023-03-13 11:26:42 | 2023-03-13 11:26:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
typedef pair<int, ll> P;
#define fi first
#define se second
const int N = 1e5 + 5;
const int M = 5e5 + 5;
int n, m;
vector <P> q[N];
ll ans[M];
struct Tree
{
vector <P> G[N];
int fa[N], siz[N], son[N], dep[N];
ll dis[N];
int top[N], tim, dfn[N], id[N];
void dfs1(int u, int p)
{
fa[u] = p, siz[u] = 1, dep[u] = dep[p] + 1;
for(auto v : G[u])
{
if(v.fi == p) continue;
dis[v.fi] = dis[u] + v.se;
dfs1(v.fi, u); siz[u] += siz[v.fi];
if(siz[v.fi] > siz[son[u]]) son[u] = v.fi;
}
return;
}
void dfs2(int u, int tp)
{
top[u] = tp, dfn[u] = ++tim, id[tim] = u;
if(son[u]) dfs2(son[u], tp);
for(auto v : G[u])
if(v.fi != fa[u] && v.fi != son[u]) dfs2(v.fi, v.fi);
return;
}
int LCA(int x, int y)
{
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x, y);
x = fa[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
ll Dis(int x, int y)
{
if(!x || !y) return 0;
return dis[x] + dis[y] - dis[LCA(x, y)] * 2;
}
} A, B;
struct Path
{
P s, t; ll dis;
Path(P _s = {0, 0}, P _t = {0, 0}) {s = _s, t = _t, dis = B.Dis(s.fi, t.fi) + s.se + t.se;}
bool operator < (const Path &rhs) const {return dis < rhs.dis;}
friend Path operator + (Path x, Path y)
{
Path z = max(x, y);
z = max({z, Path(x.s, y.s), Path(x.s, y.t)});
z = max({z, Path(x.t, y.s), Path(x.t, y.t)});
return z;
}
};
#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define mid ((l + r) >> 1)
Path t[N << 2];
ll tag[N << 2];
void pushtag(int rt, ll v)
{
t[rt].s.se += v, t[rt].t.se += v;
if(t[rt].t.fi) t[rt].dis += 2 * v;
tag[rt] += v;
}
void pushdown(int rt)
{
if(!tag[rt]) return;
pushtag(ls, tag[rt]), pushtag(rs, tag[rt]);
tag[rt] = 0;
}
void build(int l, int r, int rt)
{
if(l == r) return t[rt] = Path({A.id[l], A.dis[A.id[l]]}, {0, 0}), void();
build(l, mid, ls), build(mid + 1, r, rs);
t[rt] = t[ls] + t[rs];
}
void upd(int L, int R, int v, int l = 1, int r = n, int rt = 1)
{
if(L > R || l > R || r < L) return;
if(L <= l && r <= R) return pushtag(rt, v);
pushdown(rt);
upd(L, R, v, l, mid, ls), upd(L, R, v, mid + 1, r, rs);
t[rt] = t[ls] + t[rs];
}
void update(int l, int r, int v)
{
upd(1, n, v), upd(l, r, -2 * v);
}
ll qry(int x)
{
return max(B.Dis(x, t[1].s.fi) + t[1].s.se, B.Dis(x, t[1].t.fi) + t[1].t.se);
}
void dfs3(int u)
{
for(auto p : q[u]) ans[p.se] = qry(p.fi);
for(auto v : A.G[u])
{
if(v.fi == A.fa[u]) continue;
P ts = t[1].s, tt = t[1].t;
update(A.dfn[v.fi], A.dfn[v.fi] + A.siz[v.fi] - 1, v.se);
dfs3(v.fi);
update(A.dfn[v.fi], A.dfn[v.fi] + A.siz[v.fi] - 1, -v.se);
}
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
for(int i = 1, u, v, w; i < n; i++)
cin >> u >> v >> w, A.G[u].push_back({v, w}), A.G[v].push_back({u, w});
for(int i = 1, u, v, w; i < n; i++)
cin >> u >> v >> w, B.G[u].push_back({v, w}), B.G[v].push_back({u, w});
for(int i = 1, a, b; i <= m; i++)
cin >> a >> b, q[a].push_back({b, i});
A.dfs1(1, 0), A.dfs2(1, 1);
B.dfs1(1, 0), B.dfs2(1, 1);
build(1, n, 1); dfs3(1);
for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 33500kb
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: 1ms
memory: 34568kb
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: 0ms
memory: 33068kb
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: 52ms
memory: 37900kb
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:
633782135171 616489177187 514273941704 637066393138 462495763607 645842915960 641537859258 573604504956 634030959481 803875451466 674370549986 734764046916 744862815441 763778393516 553499885160 526743824759 610373719514 689550247042 549161302822 726811438160 653134244120 666761991962 701575393972 6...
result:
wrong answer 1st numbers differ - expected: '647838384844', found: '633782135171'