QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#159173#7103. Red Black Treeucup-team870#AC ✓1444ms37640kbC++174.9kb2023-09-02 17:35:042023-09-02 17:35:06

Judging History

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

  • [2023-09-02 17:35:06]
  • 评测
  • 测评结果:AC
  • 用时:1444ms
  • 内存:37640kb
  • [2023-09-02 17:35:04]
  • 提交

answer

#include <bits/stdc++.h>
#define For(i,l,r) for(int i=l; i<=r; i++)
using namespace std;
int read(){
    int x=0,fh=1; char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if (ch=='-') fh=1;
    for(;isdigit(ch);ch=getchar()) x=x*10+(ch^48);
    return x*fh;
}
const int N=1e5+5;
int to[N<<1],nex[N<<1],head[N],e,dfn[N],dep[N]; long long ew[N<<1];
void add(int x,int y,int z){
    to[++e]=y; nex[e]=head[x]; head[x]=e; ew[e]=z;
}
namespace LCA{
    int dfnn,lg2[N<<1],q[N<<1],pl[N],st[18][N<<1],cnt;
    void dfs(int x,int fa,int de){
        dfn[x]=++dfnn;
        dep[x]=de; cnt++;
        if (!pl[x]) pl[x]=cnt; q[cnt]=x;
        for(int i=head[x];i;i=nex[i]){
            if (to[i]!=fa) dfs(to[i],x,de+1),q[++cnt]=x;
        }
    }
    void init(int n,int root){
        For(i,2,n<<1) lg2[i]=lg2[i/2]+1;
        dfs(root,0,1);
        For(i,1,cnt) st[0][i]=q[i];
        For(i,1,lg2[cnt])
            For(j,1,cnt-(1<<i)+1)
                if (dep[ st[i-1][j] ]<=dep[ st[i-1][j+(1<<i-1)] ]) st[i][j]=st[i-1][j];
                else st[i][j]=st[i-1][j+(1<<i-1)];
    }
    int lca(int x,int y){
        int lg;
        x=pl[x]; y=pl[y];
        if (x>y) lg=x,x=y,y=lg;
        lg=lg2[y-x+1];
        if (dep[ st[lg][x] ]<=dep[ st[lg][y-(1<<lg)+1] ]) return st[lg][x];
        else return st[lg][y-(1<<lg)+1];
    }
    void clear(int n){
        For(i,1,n) pl[i]=0; cnt=0; dfnn=0;
    }
}
using LCA::lca;
int po[N],pl;
int red[N],d[N]; long long vw[N],dw[N];
void idfs(int x,int fa,int dd,long long y){
    vw[x]=y;
    if (red[x]) d[x]=x; else d[x]=dd;
    dw[x]=-vw[d[x]]+vw[x]; //cout<<"!!"<<vw[x]<<' '<<vw[d[x]]<<endl;
    for(int i=head[x];i;i=nex[i]) if (to[i]!=fa){
        idfs(to[i],x,d[x],y+ew[i]);
    }
}
bool ppf[N]; int c[N];
namespace newtree{
    int to[N<<2],nex[N<<2],head[N],e;
    int st[N],top;
    long long l,r,mid,ocnt,now[N<<2];
    bool cmd(int x,int y){
        return dfn[x]<dfn[y];
    }
    void add(int x,int y){
        //cout<<"#"<<' '<<x<<' '<<y<<endl;
        to[++e]=y; nex[e]=head[x]; head[x]=e;
    }
    int build(){
        e=0; top=0;
        sort(po+1,po+1+pl,cmd);
        st[++top]=po[1];
        int cnt=1;
        while(cnt<pl){
            //cout<<'~'<<cnt<<endl;
            int now=po[++cnt],lc=lca(st[top],now); //cout<<'~'<<cnt<<' '<<lc<<endl;
            while(dep[lc]<dep[ st[top-1] ]){
                add(st[top-1],st[top]); --top;
            }
            if (lc==st[top]) st[++top]=now;
            else if (dep[lc]>dep[ st[top-1] ]){
                add(lc,st[top]); --top; st[++top]=lc; st[++top]=now;
            }
            else if (lc==st[top-1]){
                add(lc,st[top]); --top; st[++top]=now;
            }
        }
        while(top>1){
            add(st[top-1],st[top]); --top;
        }
        return st[1];
    }
    void clear(int x){
        for(int i=head[x];i;i=nex[i]) clear(to[i]);
        head[x]=0;
    }
    bool dfs(int x,int fa){
        now[x]=0; c[x]=0;
        if (ppf[x]) ++c[x];
        bool redf;
        for(int i=head[x];i;i=nex[i]) if (to[i]!=fa){
            int y=to[i]; redf=dfs(y,x);
            if (!redf&&c[y]) c[x]+=c[y],now[x]=max(now[x],now[y]-vw[x]+vw[y]);
        }
        if (red[x]) {c[x]=0; return 1;}
        else if (c[x]&&now[x]-vw[fa]+vw[x]>mid) {c[x]=0; ++ocnt; return 1;}
        else return 0;
    }
    void work(){
        int root=build();
        //dp
        l=0,r=0; r=r*r;
        For(i,1,pl) r=max(r,dw[po[i]]);
        while(l<r){
            mid=(l+r)>>1; ocnt=0;
            dfs(root,0);
            if (ocnt<=1) r=mid;
            else l=mid+1;
        }
        printf("%lld\n",l); //cout<<endl;
        clear(root);
    }
}
bool pf[N];
int main(){
    int _=read(),x,y,z;
    while(_--){
        int n=read(),m=read(),k=read();
        //clear
        For(i,1,n) head[i]=0,red[i]=0; e=0;
        LCA::clear(n);
        //init
        For(i,1,m) x=read(),red[x]=1;
        For(i,1,n-1) x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
        LCA::init(n,1);
        //cout<<"##"<<endl;
        idfs(1,0,0,0);
        //cout<<"@@"<<endl;
        //
        while(k--){
            //build
            pl=read();
            For(i,1,pl) po[i]=read(),ppf[po[i]]=pf[ po[i] ]=1;
            int tmp=pl;
            For(i,1,tmp) if (!pf[ d[po[i]] ]){
                pf[ d[po[i]] ]=1; po[++pl]=d[po[i]];
            }
            //cout<<"!!"<<pl<<endl;
            //For(i,1,pl) cout<<po[i]<<' '; cout<<endl;
            newtree::work();
            For(i,1,pl) ppf[po[i]]=pf[po[i]]=0;
        }
    }
}
/*
9
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

9 3 1
1 4 5
1 2 1
2 3 1
3 4 1
3 5 1
4 6 0
4 7 0
5 8 0
5 9 0
5 2 6 7 8 9
*/

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 22308kb

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: 0
Accepted
time: 1444ms
memory: 37640kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

148616264
148616264
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

ok 577632 lines

Extra Test:

score: 0
Extra Test Passed