求问为何RE
查看原帖
求问为何RE
538683
Enoch006楼主2025/7/22 21:23

从loj上把#11#20都下了下来,windows 下能跑出来,请问为什么会RE呀?代码如下:

#include <bits/stdc++.h>
#define int long long
#define y1 y3
#define maxm 200005
#define maxn 1005
#define mod 1000000007
#define msk cerr
#define inf 0x3f3f3f3f3f3f3f
using namespace std;
int T,n,N,m,ans;
struct node{int to,nxt,w;}e[maxm<<1];
int h[maxm],star;
void link(int x,int y,int z){e[++star]=(node){y,h[x],z};h[x]=star;}
int dep[maxm],d[maxm],dfn[maxm],st[20][maxm],fa[20][maxm],dcnt,cnt;
void Dfs(int x,int fath,int z){
    st[0][++dcnt]=fath;dfn[x]=dcnt;dep[x]=z;
    fa[0][x]=fath;d[x]=d[fath]+1;
    for(int i=1;i<=__lg(d[x]+1)+1;i++)fa[i][x]=fa[i-1][fa[i-1][x]];
    for(int i=h[x];i;i=e[i].nxt){
        int y=e[i].to,w=e[i].w;
        if(y==fath)continue;
        Dfs(y,x,z+w);
    }
}
int CMP(int x,int y){return dfn[x]<dfn[y]?x:y;}
int LCA(int x,int y){
    if(x==y)return x;
    x=dfn[x];y=dfn[y];
    if(x>y)swap(x,y);
    int k=__lg(y-x++);
    return CMP(st[k][x],st[k][y-(1<<k)+1]);
}
int dis(int x,int y){return (!x||!y)?0:dep[x]+dep[y]-2*dep[LCA(x,y)];}
struct ysn{
    int i,x,w;
    void init(){w=-inf;}
}Inf;
vector<ysn>add[maxm];
vector<int>adi[maxm],dei[maxm];
struct sgr{
    ysn x,y;int w;
    friend bool operator <(sgr x,sgr y){return x.w>y.w;}
    void init(){x.init();y.init();w=-inf-inf;}
}tmp[6];
int calc(int x,int y,int w1,int w2){return dis(x,y)+w1+w2;}
int Find(int x,int k){for(int i=__lg(k+1)+1;i>=0;i--)if((1<<i)<=k)k-=1<<i,x=fa[i][x];return x;}
int MX;
sgr operator +(sgr x,sgr y){
    int x1=x.x.x,x2=x.y.x,y1=y.x.x,y2=y.y.x;
    int wx1=x.x.w,wx2=x.y.w,wy1=y.x.w,wy2=y.y.w;
    int ix1=x.x.i,ix2=x.y.i,iy1=y.x.i,iy2=y.y.i;
    sgr z=x;
    tmp[1].init();tmp[2].init();tmp[3].init();tmp[4].init();tmp[5].init();
    if(ix1!=iy1)tmp[1]={{ix1,x1,wx1},{iy1,y1,wy1},calc(x1,y1,wx1,wy1)};
    if(ix1!=iy2)tmp[2]={{ix1,x1,wx1},{iy2,y2,wy2},calc(x1,y2,wx1,wy2)};
    if(ix2!=iy1)tmp[3]={{ix2,x2,wx2},{iy1,y1,wy1},calc(x2,y1,wx2,wy1)};
    if(ix2!=iy2)tmp[4]={{ix2,x2,wx2},{iy2,y2,wy2},calc(x2,y2,wx2,wy2)};
    tmp[5]={{iy1,y1,wy1},{iy2,y2,wy2},calc(y1,y2,wy1,wy2)};
    if(z.w<tmp[1].w)z=tmp[1];
    if(z.w<tmp[2].w)z=tmp[2];
    if(z.w<tmp[3].w)z=tmp[3];
    if(z.w<tmp[4].w)z=tmp[4];
    if(z.w<tmp[5].w)z=tmp[5];
    return z;
}
int tot,ver[maxm];
struct Seg{
    int l,r;
    sgr mx;
}t[maxm*25];
#define ls t[k].l
#define rs t[k].r
void Pushup(int k){t[k].mx=t[ls].mx+t[rs].mx;}
sgr Add(sgr x,ysn y){
    int x1=x.x.x,x2=x.y.x,y1=y.x;
    int wx1=x.x.w,wx2=x.y.w,wy1=y.w;
    int ix1=x.x.i,ix2=x.y.i,iy1=y.i;
    sgr z=x;tmp[1].init();tmp[2].init();
    if(ix1!=iy1)tmp[1]={{ix1,x1,wx1},{iy1,y1,wy1},calc(x1,y1,wx1,wy1)};
    if(ix2!=iy1)tmp[2]={{ix2,x2,wx2},{iy1,y1,wy1},calc(x2,y1,wx2,wy1)};
    MX=max({MX,tmp[1].w,tmp[2].w});
    if(z.w<tmp[1].w)z=tmp[1];
    if(z.w<tmp[2].w)z=tmp[2];
    return z;
}
int X;
void Insert(int &k,int l,int r,int x,ysn y){
    if(!k)k=++tot,t[k].l=t[k].r=0,t[k].mx.init();
    t[k].mx=Add(t[k].mx,y);
    // if(X==8)msk<<MX<<"\n";
    if(l==r)return;
    int mid=l+r>>1;
    if(mid>=x)Insert(ls,l,mid,x,y);
    else Insert(rs,mid+1,r,x,y);
}
void Del(int k,int l,int r,int x){
    if(l==r)return t[k].mx.init();
    int mid=l+r>>1;
    if(mid>=x)Del(ls,l,mid,x);
    else Del(rs,mid+1,r,x);
    Pushup(k);
}
void Merge(int &x,int y,int l,int r){
    if(!x||!y)return void(x+=y);
    Add(t[x].mx,t[y].mx.x);Add(t[x].mx,t[y].mx.y);
    if(l==r)return void(t[x].mx=t[x].mx+t[y].mx);
    int mid=l+r>>1;
    Merge(t[x].l,t[y].l,l,mid);
    Merge(t[x].r,t[y].r,mid+1,r);
    Pushup(x);
}
void pri(int k,int l,int r){
    if(!k)return;
    msk<<"["<<l<<","<<r<<"]:"<<t[k].mx.w<<" x:"<<t[k].mx.x.i<<" "<<t[k].mx.x.w<<" y:"<<t[k].mx.y.i<<" "<<t[k].mx.y.w<<"\n";
    if(l==r)return;
    int mid=l+r>>1;pri(ls,l,mid);pri(rs,mid+1,r);
}
void Sol(int x,int fath){
    for(int i=h[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fath)continue;
        Sol(y,x);
    }
    MX=-inf;
    for(int i=h[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fath)continue;
        Merge(ver[x],ver[y],1,N);
    }
    X=x;
    // if(x==8)msk<<x<<" "<<tot<<" "<<MX<<"=========\n";
    for(int i=0;i<add[x].size();i++){
        int id=adi[x][i];ysn y=add[x][i];
        Insert(ver[x],1,N,id,y);
        // if(x==8)msk<<"ins "<<id<<":"<<y.i<<" "<<y.x<<" "<<y.w<<" "<<MX<<"\n";
    }
    // pri(ver[x],1,m);
    // if(x==8)msk<<"ans:"<<MX-2*dep[x]<<"\n";
    ans=max(ans,MX-2*dep[x]);
    for(int i=0;i<dei[x].size();i++){
        int id=dei[x][i];
        // if(x==8) msk<<"del "<<id<<"\n";
        Del(ver[x],1,N,id);
    }
}
struct Q{int x,y,z;}q[maxm];
signed main(){	
//	 freopen("20.in","r",stdin);
//	 freopen("wrong.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>T;Inf.init();int Min=-inf/5;t[0].mx.init();
    while(T--){
        star=dcnt=cnt=tot=0;ans=-inf;
        for(int i=1;i<=2*max(n,m);i++)h[i]=ver[i]=0,
            add[i].clear(),adi[i].clear(),dei[i].clear();
        cin>>n;        
        for(int i=1;i<n;i++){
            int x,y,z;cin>>x>>y>>z;
            link(x,y,z);link(y,x,z);
        }
        Dfs(1,0,0);
        for(int j=1;j<=__lg(n+1)+1;j++)for(int i=1;i+(1<<j)-1<=n;i++)
            st[j][i]=CMP(st[j-1][i],st[j-1][i+(1<<j-1)]);
        // for(int i=1;i<=n;i++)msk<<i<<":"<<dep[i]<<"\n";
        cin>>m;
        for(int i=1;i<=m;i++)cin>>q[i].x>>q[i].y>>q[i].z;
        for(int i=1;i<=m;i++){
            int x=q[i].x,y=q[i].y,z=q[i].z;
            if(x!=LCA(x,y)){
                int w=dis(x,y)-2*z+dep[x];
                add[x].push_back({i,y,w});
                adi[x].push_back(i);
                int di=d[x]-d[LCA(x,y)]-1,pa=Find(x,di);
                dei[pa].push_back(i);
                // msk<<i<<" "<<x<<" "<<y<<" "<<pa<<" "<<w<<"\n";
            }
            swap(x,y);
            if(x!=LCA(x,y)){
                int w=dis(x,y)-2*z+dep[x];
                add[x].push_back({i,y,w});
                adi[x].push_back(i+m);
                int di=d[x]-d[LCA(x,y)]-1,pa=Find(x,di);
                dei[pa].push_back(i+m);
                // msk<<i<<" "<<x<<" "<<y<<" "<<pa<<" "<<w<<"\n";
            }
        }
        N=m<<1;
        Sol(1,0);
        if(ans<=Min)cout<<"F\n";
        else cout<<(ans>>1)<<"\n";
    }
//	while(1);
    return 0;
}
2025/7/22 21:23
加载中...