QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694236#5439. Meet in the MiddleDEMONKILLERWA 0ms22652kbC++204.2kb2024-10-31 17:31:482024-10-31 17:31:50

Judging History

你现在查看的是最新测评结果

  • [2024-10-31 17:31:50]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:22652kb
  • [2024-10-31 17:31:48]
  • 提交

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();
}

详细

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'