震惊!随机选分治中心竟然可过!
  • 板块P4178 Tree
  • 楼主ethan_zhou
  • 当前回复7
  • 已保存回复7
  • 发布时间2021/4/25 21:19
  • 上次更新2023/11/5 00:07:34
查看原帖
震惊!随机选分治中心竟然可过!
124740
ethan_zhou楼主2021/4/25 21:19

rt,刚刚想把这题代码改改交到别的地方,结果发现一直t,拿到本地编译了一下,报了个 warning,才发这题我在求重心时,所用的 sz 数组都是没有初始化的!!!

void calsz(int p,int fa){
    sz[p]=1;
    for(int i=0,nx;i<(int)e[p].size();i++){
        //此处nx没有赋值,甚至没有初始化,正常应该赋值为e[p][i].fi
        if(vis[nx] || nx==fa)continue;
        calsz(nx,p);
        sz[p]+=sz[nx];
    }
}
int calrt(int p,int fa,int tot){
    bool f=(tot<=(sz[p]<<1));
    for(int tmp,nx,i=0;i<(int)e[p].size();i++){
        nx=e[p][i].fi;
        if(vis[nx] || nx==fa)continue;
        f&=(tot>=(sz[nx]<<1));
        tmp=calrt(nx,p,tot);
        if(~tmp)return tmp;
    }
    return f?p:-1;
}
2021/4/25 21:19
加载中...