QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87475 | #5439. Meet in the Middle | Acestar | WA | 47ms | 36800kb | C++14 | 3.3kb | 2023-03-13 09:51:50 | 2023-03-13 09:51:53 |
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)
{
Path p = t[1];
return max(B.Dis(x, p.s.fi) + p.s.se, B.Dis(x, p.t.fi) + p.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;
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 32728kb
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: 0ms
memory: 34536kb
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: 34548kb
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: 47ms
memory: 36800kb
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 641998753292 573604504956 634030959481 803875451466 674831444020 734764046916 745800835759 764716413834 553960779194 527204718793 611311739832 690011141076 549622196856 726811438160 654072264438 666761991962 701575393972 6...
result:
wrong answer 1st numbers differ - expected: '647838384844', found: '633782135171'