卡40分,求助(
查看原帖
卡40分,求助(
113190
Qiuly楼主2020/5/11 15:06

Loj 上可过,跑得飞快。

本地对拍奇慢无比,表示不解。

Luogu 后三个点卡得自闭,求助(

感觉做法假掉了,不知道哪里假了(

RI L=1;
for(RI i=1;i<=lim;++i)
    for(RI j=1;j<=n;++j)
        dsu[i].fa[j]=j,dsu[i].siz[j]=1,
        dsu[i].va[j]=dsu[i].vb[j]=-1;

for(RI t=1;t<=q;++t) {
    while(L<=m&&G[L].b<=Q[t].b) {
        for(RI t=bol[G[L].rk];t<=lim;++t)
            dsu[t].merge(G[L].u,G[L].v,G[L].a,G[L].b);
        use[G[L].rk]=true,++L;
    }
    RI l=1,r=m,mid,res=0;
    while(l<=r) (tmp[mid=l+r>>1]<=Q[t].a)?(res=mid,l=mid+1):r=mid-1;
    RI ID=bol[res]-1;
    if(ID<1) {ans[Q[t].id]=false;continue;}
    
    nowID=ID;
    for(int i=nxt[ID]+1;i<=res;++i) {
        if(G[pos[i]].a>Q[t].a) break;
        if(use[i]==true)
            dsu[ID].Merge(G[pos[i]].u,G[pos[i]].v,G[pos[i]].a,G[pos[i]].b);
    }
    int _s=dsu[ID].find(Q[t].s),_t=dsu[ID].find(Q[t].t);
    ans[Q[t].id]=(bool)(_s==_t&&dsu[ID].va[_s]==Q[t].a&&dsu[ID].vb[_s]==Q[t].b);
    back();
}
for(int i=1;i<=q;++i) puts(ans[i]==1?"Yes":"No");
2020/5/11 15:06
加载中...