QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694781 | #5439. Meet in the Middle | hewanying | WA | 0ms | 18056kb | C++14 | 3.2kb | 2024-10-31 18:38:58 | 2024-10-31 18:39:04 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=1e5+5,M=5e5+5;
int n,m;
ll ans[M];
struct Nod{int x,id;};
vector<Nod> Q[N];
struct Edge{int v;ll w;};
namespace Tr{
vector<Edge> G[N];
int dfn[N],idx=0,st[20][N];
ll d[N];
void add(int u,int v,int w){G[u].pb({v,w}),G[v].pb({u,w});}
void dfs(int u,int fa){
dfn[u]=++idx,st[0][idx]=fa;
for(auto i:G[u]) if(i.v!=fa) d[i.v]=d[u]+i.w,dfs(i.v,u);
}
int Min(int u,int v){return dfn[u]<dfn[v]?u:v;}
void init(){
for(int i=1;i<=n;i++) dfn[i]=d[i]=0,G[i].clear();
for(int i=1,u,v,w;i<n;i++) cin>>u>>v>>w,G[u].pb({v,w}),G[v].pb({u,w});
idx=0;
dfs(1,0);
for(int i=1;i<=__lg(n)+1;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
st[i][j]=Min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
int LCA(int u,int v){
if(u==v) return u;
u=dfn[u],v=dfn[v];
if(u>v) swap(u,v);
int s=__lg(v-u);
return Min(st[s][u+1],st[s][v-(1<<s)+1]);
}
ll dis(int u,int v){return d[u]+d[v]-2ll*d[LCA(u,v)];}
}
namespace SGT{
vector<Edge> G[N];
int dfn[N],idx=0,rev[N],ed[N];
ll d[N];
void dfs(int u,int fa){
rev[dfn[u]=++idx]=u;
for(auto i:G[u]) if(i.v!=fa) d[i.v]=d[u]+i.w,dfs(i.v,u);
ed[u]=idx;
}
#define mid ((l+r)>>1)
#define lc p<<1
#define rc p<<1|1
#define lson l,mid,lc
#define rson mid+1,r,rc
struct pnt{int x;ll dx;};
ll dis(pnt a,pnt b){
if(a.x==b.x) return max(a.dx,b.dx);
return Tr::dis(a.x,b.x)+a.dx+b.dx;
}
struct sgt{
pnt a,b;
}tr[N<<2];
ll tg[N<<2];
sgt operator + (sgt x,sgt y){
sgt z=dis(x.a,x.b)>dis(y.a,y.b)?x:y;
for(auto i:{x.a,x.b}) for(auto j:{y.a,y.b})
if(dis(i,j)>dis(z.a,z.b)) z={i,j};
return z;
}
void pu(int p){tr[p]=tr[lc]+tr[rc];}
void pt(int p,ll v){tg[p]+=v,tr[p].a.dx+=v,tr[p].b.dx+=v;}
void pd(int p){if(tg[p]!=0) pt(lc,tg[p]),pt(rc,tg[p]),tg[p]=0;}
void upd(int l,int r,int p,int x,int y,ll v){
if(x<=l&&y>=r) return pt(p,v);
pd(p);
if(x<=mid) upd(lson,x,y,v);
if(y>mid) upd(rson,x,y,v);
pu(p);
}
void build(int l,int r,int p){
tg[p]=0;
if(l==r) return tr[p].a=tr[p].b={rev[l],d[rev[l]]},void();
build(lson),build(rson),pu(p);
}
void mof(int l,int r,ll v){
upd(1,n,1,l,r,v);
if(l>1) upd(1,n,1,1,l-1,-v);
if(r<n) upd(1,n,1,r+1,n,-v);
}
void solve(int u,int fa){
for(auto i:Q[u]) ans[i.id]=max(dis(tr[1].a,(pnt){i.x,0}),dis(tr[1].b,(pnt){i.x,0}));
for(auto i:G[u]) if(i.v!=fa){
mof(dfn[i.v],ed[i.v],-i.w);
solve(i.v,u);
mof(dfn[i.v],ed[i.v],i.w);
}
}
void init(){
for(int i=1;i<=n;i++) dfn[i]=rev[i]=d[i]=ed[i]=0,G[i].clear(),Q[i].clear();
idx=0;
for(int i=1,u,v,w;i<n;i++) cin>>u>>v>>w,G[u].pb({v,w}),G[v].pb({u,w});
Tr::init(),dfs(1,0),build(1,n,1);
cin>>m;
for(int i=1,u,v;i<=m;i++) cin>>u>>v,Q[u].pb({v,i});
solve(1,0);
for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
}
}
void SOLVE(){
cin>>n;
SGT::init();
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
SOLVE();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 18056kb
input:
3 4 1 2 1 2 3 2 1 2 2 2 3 1 1 1 1 2 2 1 2 2
output:
12
result:
wrong answer 1st numbers differ - expected: '6', found: '12'