Submission #598072

#	Time	Username	Problem	Language	Result	Execution time	Memory
598072		alirezasamimi100	Dreaming (IOI13_dreaming)	C++17	100 / 100	178 ms	21464 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using pii = pair<int,int>;
#define F first
#define S second
#define lc v<<1
#define rc v<<1|1

const int N = 1e5 + 10, inf = 1.05e9;

int n,m,f[N*4],lz[N*4],t,st[N],fn[N],fl[N],di,h[N];
pii mn;
vector<pii> adj[N],ans;
void build(int v, int l, int r){
    lz[v]=0;
    if(r-l==1){
        f[v]=h[l];
        return;
    }
    int m=(l+r)>>1;
    build(lc,l,m);
    build(rc,m,r);
    f[v]=max(f[lc],f[rc]);
}
void shift(int v, int l, int r){
    f[v]+=lz[v];
    if(r-l>1){
        lz[lc]+=lz[v];
        lz[rc]+=lz[v];
    }
    lz[v]=0;
}
void upd(int v, int l, int r, int tl, int tr, int x){
    shift(v,l,r);
    if(tl>=r || l>=tr || tl>=tr) return;
    if(l>=tl && r<=tr){
        lz[v]=x;
        return shift(v,l,r);
    }
    int m=(l+r)>>1;
    upd(lc,l,m,tl,tr,x);
    upd(rc,m,r,tl,tr,x);
    f[v]=max(f[lc],f[rc]);
}
int get(int v, int l, int r, int tl, int tr){
    shift(v,l,r);
    if(tl>=r || l>=tr || tl>=tr) return 0;
    if(l>=tl && r<=tr) return f[v];
    int m=(l+r)>>1;
    return max(get(lc,l,m,tl,tr),get(rc,m,r,tl,tr));
}
void dfs(int v){
    st[v]=t;
    fl[v]=1;
    for(auto [u,w] : adj[v]){
        if(fl[u]) continue;
        h[++t]=h[st[v]]+w;
        dfs(u);
    }
    fn[v]=t;
}
void sfd(int v, int p){
    di=max(di,f[1]);
    if(f[1]<mn.F) mn={f[1],v};
    for(auto [u,w] : adj[v]){
        if(u==p) continue;
        upd(1,0,t+1,0,t+1,w);
        upd(1,0,t+1,st[u],fn[u]+1,-2*w);
        sfd(u,v);
        upd(1,0,t+1,0,t+1,-w);
        upd(1,0,t+1,st[u],fn[u]+1,2*w);
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N;
    m=M;
    for(int i=0; i<m; i++){
        adj[A[i]].pb({B[i],T[i]});
        adj[B[i]].pb({A[i],T[i]});
    }
    for(int i=0; i<n; i++){
        if(fl[i]) continue;
        t=0;
        mn={inf,-1};
        dfs(i);
        build(1,0,t+1);
        sfd(i,-1);
        ans.pb(mn);
    }
    sort(ans.begin(),ans.end(),greater<>());
    int k = ans.size();
    if(k==1) return di;
    if(k==2) return max(di,ans[0].F+ans[1].F+L);
    return max({di,ans[0].F+ans[1].F+L,ans[1].F+ans[2].F+2*L});
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23