Submission #275956

#	Time	Username	Problem	Language	Result	Execution time	Memory
275956		ainta	Mountains and Valleys (CCO20_day1problem3)	C++17	25 / 25	5543 ms	252348 KiB

Main

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define N_ 510000
#define SZ 524288
typedef pair<int,int> pii;
int n, m, res, C[N_], PPP[N_], Num[N_], Ed[N_], Dep[N_], ord[N_];
vector<int>E[N_], Ch[N_];
struct Edge{
    int e, d;
};
int Dis[N_], par[N_], D[N_], D2[N_], chk[N_], MD2[N_];
int UD[N_], UD2[N_], UMD2[N_];
int MM1[N_][4], MM2[N_][4];
int MPV1[N_][4], MPV2[N_][4];
struct AA{
    int a, b, c;
};
void DFS(int a, int pp, int d){
    Dis[a]=d;
    par[a]=pp;
    for(auto &x : E[a]){
        if(x!=pp)DFS(x,a,d+1);
    }
}
void DFS2(int a, int pp){
    D[a]=D2[a]=MD2[a]=0;
    par[a]=pp;
    C[a]=1;
    for(auto &x : E[a]){
        if(x==pp||chk[x])continue;
        Dep[x]=Dep[a]+1;
        DFS2(x,a);
        C[a]+=C[x];
        D2[a]=max(D2[a],D[a]+D[x]+1);
        D[a]=max(D[a],D[x]+1);
        MD2[a]=max(MD2[a],MD2[x]);
    }
    MD2[a]=max(MD2[a],D2[a]);
}
void UDT(int *M, int *pv, int a, int b, int sz){
    int i, j;
    for(i=0;i<sz;i++){
        if(M[i]<a){
            for(j=sz-1;j>i;j--){
                M[j]=M[j-1];
                pv[j]=pv[j-1];
            }
            M[i]=a,pv[i]=b;
            break;
        }
    }
}
void DFS3(int a, int pp){
    for(auto &x : E[a]){
        if(x==pp)continue;
        Ch[a].push_back(x);
    }
    int Mx[3]={-5,-5,-5},px[3]={-1,-1,-1};
    int Mx2[2]={-1,-1}, px2[2]={-1,-1};
    if(pp){
        UDT(Mx,px,UD[a],pp,3);
        UDT(Mx2,px2,UMD2[a],pp,2);
    }
    UDT(Mx,px,-1,a,3);
    for(auto &x : Ch[a]){
        UDT(Mx, px, D[x],x,3);
        UDT(Mx2,px2,MD2[x],x,2);
    }
    int i;
    for(auto &x : Ch[a]){
        int d1=-1,d2=-1;
        int M1=-5,M2=-5;
        for(i=0;i<3;i++){
            if(px[i]!=x){
                if(M1==-5)M1=Mx[i];
                else if(M2==-5)M2=Mx[i];
            }
        }
        for(i=0;i<2;i++){
            if(px2[i]!=x){
                d2=Mx2[i];
                break;
            }
        }
        UD[x]=M1+1;
        d2=max(d2,UD[x]);
        if(M1!=-5 && M2!=-5)d2=max(d2, M1+M2+2);
        UMD2[x] = d2;
    }
    for(auto &x : Ch[a])DFS3(x,a);
}

pii Calc(int a, int p1, int p2){
    int i, r2=0;
    int z1=-1,z2=-1;
    for(i=0;i<4;i++){
        if(MPV1[a][i]!=p1&&MPV1[a][i]!=p2){
            if(z1==-1)z1=MM1[a][i];
            else if(z2==-1)z2=MM1[a][i];
        }
        if(MPV2[a][i]!=p1&&MPV2[a][i]!=p2){
            r2=max(r2,MM2[a][i]);
        }
    }
    if(z1!=-1 && z2!=-1)r2 = max(r2,z1+z2);
    if(z1<0)z1=0;
    return pii(z1,r2);
}
int cnt;
void HLD(int a, int ppp){
    Num[a]=++cnt;
    ord[cnt]=a;
    PPP[a]=ppp;
    int Mx=-1,pv=-1;
    for(auto &x : Ch[a]){
        if(Mx<C[x]){
            Mx=C[x],pv=x;
        }
    }
    if(pv!=-1){
        HLD(pv,ppp);
    }
    for(auto &x : Ch[a]){
        if(pv!=x)HLD(x,x);
    }
    Ed[a]=cnt;
}
pii DD[N_], DD2[N_], DD3[N_];
int Pre2[N_], DPre[N_];
struct BB{
    int top, bot;
}Pre1[N_];
struct Node{
    int top, bot;
    int g;
    int d2;
}IT[SZ+SZ];
int INF = 1e9;
Node Merge(Node a, Node b){
    Node r;
    r.top=max(a.top,b.top);
    r.bot=max(a.bot,b.bot);
    r.g=max(max(a.g,b.g),a.top+b.bot);
    r.d2=max(a.d2,b.d2);
    return r;
}
Node GetNode(int b, int e){
    b+=SZ,e+=SZ;
    vector<int>A,B;
    while(b<=e){
        if(b&1)A.push_back(b);
        if(!(e&1))B.push_back(e);
        b=(b+1)>>1,e=(e-1)>>1;
    }
    reverse(B.begin(),B.end());
    int ck=0;
    Node res;
    for(auto &t : A){
        if(!ck){
            ck=1;
            res=IT[t];
            continue;
        }
        else res=Merge(res,IT[t]);
    }
    for(auto &t : B){
        if(!ck){
            ck=1;
            res=IT[t];
            continue;
        }
        else res=Merge(res,IT[t]);
    }
    return res;
}
void ITPut(int a, int tt, int bb, int d2){
    a+=SZ;
    IT[a]={tt,bb,-INF,d2};
    while(a!=1){
        a>>=1;
        IT[a]=Merge(IT[a*2],IT[a*2+1]);
    }
}
int LCA(int a, int b){
    while(PPP[a]!=PPP[b]){
        if(Num[PPP[a]]<Num[PPP[b]])b=par[PPP[b]];
        else a=par[PPP[a]];
    }
    if(Dep[a]<Dep[b])return a;
    return b;
}
int MM;
int GoPath(int a, int l, int &cl){
    int t = a, bef = -1;
    int MB = -1e9;
    while(1){
        if(t==l){
            cl=bef;
            break;
        }
        pii z;
        int bb, ee;
        if(a==t){
            z = DD3[a];
        }
        else{
            z = DD2[bef];
        }
        MM=max(MM,z.second);
        int bot1 = z.first-Dep[t]+1,top1=z.first+Dep[t]+1;
        MM=max(MM,top1+MB);
        MB=max(MB,bot1);

        if(PPP[t]==PPP[l]){
            bb = Num[l]+1, ee = Num[t] - 1;
            cl=ord[bb];
            if(bb<=ee){
                Node tp = GetNode(bb,ee);
                MM=max(MM,max(tp.g,tp.d2));
                MM=max(MM, MB+tp.top);
                MB=max(MB,tp.bot);
            }
            break;
        }
        else{
            bb = Num[PPP[t]], ee = Num[t] - 1;
            if(bb<=ee){
                MM=max(MM,Pre2[ee]);
                MM=max(MM,DPre[ee]);
                MM=max(MM,MB+Pre1[ee].top);
                MB=max(MB,Pre1[ee].bot);
            }
        }
        bef = PPP[t];
        t=par[PPP[t]];
    }
    return MB;
}

void Go(int a, int b, int c){
    int l = LCA(a,b);
    MM=-1e9;
    int ca=-1,cb=-1;
    int MB1 = GoPath(a,l,ca);
    int MB2 = GoPath(b,l,cb);
    pii zz = Calc(l,ca,cb);
    MM=max(MM,zz.second);
    int tt = zz.first+Dep[l]+1;
//    printf("%d\n",MM);
 //   printf("%d %d\n",DD3[5].first,DD3[5].second);
 //   printf("%d %d\n",MB1,MB2);
    MM=max(MM,max(MB1,MB2)+tt);
//    printf("%d %d %d %d\n",MB1,MB2,ca,cb);
    MM=max(MM,MB1+MB2+Dep[l]*2);
//    printf("%d %d %d\n",a,b,l);

    int base = 2*(n-1)+c-(Dep[a]+Dep[b]-Dep[l]*2);
//    printf("%d %d %d %d\n",a,b,base,MM);
    res=min(res,base-MM);
}
int main(){
    int i, a, b, c, j;
    scanf("%d%d",&n,&m);
    vector<AA>V;
    for(i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        a++,b++;
        if(c==1){
            E[a].push_back(b);
            E[b].push_back(a);
        }
        else{
            V.push_back({a,b,c});
        }
    }
    DFS(1,0,0);
    int Mx=-1, x=-1, y=-1;
    for(i=1;i<=n;i++)if(Mx < Dis[i])Mx=Dis[i],x=i;
    DFS(x,0,0);
    Mx=-1;
    for(i=1;i<=n;i++)if(Mx < Dis[i])Mx=Dis[i],y=i;
    res = 2*(n-1)-Mx;

    DFS2(1,0);
    DFS3(1,0);
    HLD(1,1);

    for(i=1;i<=n;i++){
        for(j=0;j<4;j++){
            MM1[i][j]=MM2[i][j]=MPV1[i][j]=MPV2[i][j]=-1;
        }
        for(auto &x : E[i]){
            int d = D[x]+1;
            if(x==par[i])d = UD[i]+1;
            UDT(MM1[i],MPV1[i],d,x,4);
            d = MD2[x];
            if(x==par[i])d = UMD2[i];
            UDT(MM2[i],MPV2[i],d,x,4);
        }
    }
    for(i=2;i<n;i++){
        int x = ord[i];
        int y = ord[i+1];
        DD[x]=Calc(x,y,par[x]);
    }
    for(x=1;x<=n;x++){
        if(par[x])DD2[x] = Calc(par[x],x,par[par[x]]);
        DD3[x] = Calc(x,par[x],-1);
    }
    for(i=1;i<=n;i++){
        int x = ord[i];
        int z = PPP[x];
        int tt = DD[x].first + Dep[x] + 1;
        int bb = DD[x].first - Dep[x] + 1;
        if(x==z){
            Pre1[i]={tt,bb};
            Pre2[i] = DD[x].second;
            DPre[i]=-INF;
        }
        else{
            DPre[i]=max(DPre[i-1],bb+Pre1[i-1].top);
            Pre1[i]={max(tt,Pre1[i-1].top), max(bb,Pre1[i-1].bot)};
            Pre2[i] = max(Pre2[i-1],DD[x].second);
        }
        ITPut(i,tt,bb,DD[x].second);
    }
    for(auto &t : V){
        Go(t.a,t.b,t.c);
    }
    printf("%d\n",res);
}

Compilation message (stderr)

Main.cpp: In function 'void DFS3(int, int)':
Main.cpp:73:13: warning: unused variable 'd1' [-Wunused-variable]
   73 |         int d1=-1,d2=-1;
      |             ^~
Main.cpp: In function 'int main()':
Main.cpp:279:22: warning: variable 'y' set but not used [-Wunused-but-set-variable]
  279 |     int Mx=-1, x=-1, y=-1;
      |                      ^
Main.cpp:265:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  265 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:268:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  268 |         scanf("%d%d%d",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 6 / 6
• Subtask 5: 2 / 2
• Subtask 6: 3 / 3
• Subtask 7: 5 / 5
• Subtask 8: 4 / 4