QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694236 | #5439. Meet in the Middle | DEMONKILLER | WA | 0ms | 22652kb | C++20 | 4.2kb | 2024-10-31 17:31:48 | 2024-10-31 17:31:50 |
Judging History
answer
#include<bits/stdc++.h>
#define N 100010
#define Pii pair<int,int>
#define Fi first
#define Se second
#define ll long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline bool Isdigit(char c){return c>='0'&&c<='9';}
template <typename T>inline void read(T& r){
r=0;bool w=0;char ch=getchar();
while(!Isdigit(ch))w=ch=='-'?1:0,ch=getchar();
while(Isdigit(ch))r=(r<<3)+(r<<1)+(ch^48),ch=getchar();
r=w?-r:r;
}
vector<Pii> g[2][N],q[N];
ll dis[2][N],Tag[N<<2],Res[N<<3];
int T,n,Q,tot,idx,lg[N],dR[N],Rk[N],dfn[N],Pos[N],St[20][N];
void dfs1(int now,int fa){
Pos[Rk[now]=++idx]=now;
for(Pii i:g[0][now])
if(i.Fi^fa){
dis[0][i.Fi]=dis[0][now]+i.Se;
dfs1(i.Fi,now);
}
dR[now]=idx;
}
void dfs2(int now,int fa){
St[0][dfn[now]=++tot]=fa;
for(Pii i:g[1][now])
if(i.Fi^fa){
dis[1][i.Fi]=dis[1][now]+i.Se;
dfs2(i.Fi,now);
}
}
inline int Cmp(int i,int j){return dfn[i]<dfn[j]?i:j;}
void Init(){
lg[0]=-1;
for(int i=1;i<=n;i++)
lg[i]=lg[i>>1]+1;
for(int i=1;i<=18;i++)
for(int j=1;j+(1<<i)-1<=n;j++)
St[i][j]=Cmp(St[i-1][j],St[i-1][j+(1<<i-1)]);
}
inline int Get_Lca(int x,int y){
if(x==y)return x;
if(dfn[x]>dfn[y])swap(x,y);
x=dfn[x],y=dfn[y];
int k=lg[y-(x++)];
return Cmp(St[k][x],St[k][y-(1<<k)+1]);
}
inline ll Get_Dis(int x,int y){return dis[1][x]+dis[1][y]-(dis[1][Get_Lca(x,y)]*2);}
struct Seg_Tree{
int u,v;
ll x,y;
Seg_Tree(int _u=0,int _v=0,ll _x=0,ll _y=0):
u(_u),v(_v),x(_x),y(_y){}
inline ll Dis()const{return u==v?0:x+y+Get_Dis(u,v);}
inline friend Seg_Tree operator+(Seg_Tree a,Seg_Tree b){
Seg_Tree x1=Seg_Tree(a.u,b.u,a.x,b.x);
Seg_Tree x2=Seg_Tree(a.u,b.v,a.x,b.y);
Seg_Tree x3=Seg_Tree(a.v,b.u,a.y,b.x);
Seg_Tree x4=Seg_Tree(a.v,b.v,a.y,b.y);
ll Res=max({a.Dis(),b.Dis(),x1.Dis(),x2.Dis(),x3.Dis(),x4.Dis()});
if(Res==a.Dis())return a;
if(Res==b.Dis())return b;
if(Res==x1.Dis())return x1;
if(Res==x2.Dis())return x2;
if(Res==x3.Dis())return x3;
if(Res==x4.Dis())return x4;
return Seg_Tree();
}
}Tr[N<<2];
inline void Add(int p,ll c){
Tr[p].x+=c;
Tr[p].y+=c;
Tag[p]+=c;
}
inline void push_down(int p){
if(Tag[p]){
Add(lc,Tag[p]);
Add(rc,Tag[p]);
Tag[p]=0;
}
}
void build(int p,int l,int r){
Tag[p]=0;
if(l==r)
return Tr[p]=Seg_Tree(Pos[l],Pos[l],dis[0][Pos[l]],dis[0][Pos[l]]),void();
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
Tr[p]=Tr[lc]+Tr[rc];
}
void Update(int p,int l,int r,int L,int R,ll Val){
if(L<=l&&r<=R)
return Add(p,Val),void();
push_down(p);
int mid=(l+r)>>1;
if(L<=mid)Update(lc,l,mid,L,R,Val);
if(R>mid)Update(rc,mid+1,r,L,R,Val);
Tr[p]=Tr[lc]+Tr[rc];
}
void Get_Ans(int now,int fa){
for(auto [x,Id]:q[now])
Res[Id]=max(Get_Dis(Tr[1].u,x)+Tr[1].x,Get_Dis(Tr[1].v,x)+Tr[1].y);
for(auto [v,w]:g[0][now])
if(v^fa){
Add(1,w);
Update(1,1,n,Rk[v],dR[v],-2ll*w);
Get_Ans(v,now);
Add(1,-w);
Update(1,1,n,Rk[v],dR[v],2ll*w);
}
}
void Solve(){
read(n);
for(int i=1,u,v,w;i<n;i++){
read(u),read(v),read(w);
g[0][u].emplace_back(v,w);
g[0][v].emplace_back(u,w);
}
for(int i=1,u,v,w;i<n;i++){
read(u),read(v),read(w);
g[1][u].emplace_back(v,w);
g[1][v].emplace_back(u,w);
}
dfs1(1,0);
dfs2(1,0);
Init();
read(Q);
for(int i=1,u,v;i<=Q;i++){
read(u),read(v);
q[u].emplace_back(v,i);
}
build(1,1,n);
Get_Ans(1,0);
for(int i=1;i<=Q;i++)
printf("%lld\n",Res[i]);
tot=idx=0;
for(int i=1;i<=n;i++){
q[i].clear();
g[0][i].clear();
g[1][i].clear();
}
}
int main(){
// freopen("move.in","r",stdin);
// freopen("move.out","w",stdout);
T=1;
while(T--)Solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 22652kb
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'