Submission #1282380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282380		trandangquang	Dreaming (IOI13_dreaming)	C++20	100 / 100	50 ms	26544 KiB

dreaming

#include"dreaming.h"
#include<bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=1e5+5;

int n,m,l; bool vis[N];
vector<ii> adj[N],child[N];
int root[N],numRoot;
ll mxDia[N],miDia[N];
ll mx[N],ans[N],out[N],pre[N],suf[N];

void dfs(int u){
    vis[u]=true;
    for(auto [v,w]:adj[u]) if(!vis[v]){
        child[u].eb(v,w);
        dfs(v);
        maxi(mx[u],mx[v]+w);
    }
}

void reroot(int u){
    ans[u]=max(mx[u],out[u]);
//    cout<<u _ ans[u] _ out[u]<<'\n';
    maxi(mxDia[numRoot],ans[u]);
    mini(miDia[numRoot],ans[u]);

    rep(i,sz(child[u])){
        int v=child[u][i].fi, w=child[u][i].se;
        pre[i]=mx[v]+w;
        if(i>0) maxi(pre[i], pre[i-1]);
    }
    ford(i,sz(child[u])-1,0){
        int v=child[u][i].fi, w=child[u][i].se;
        suf[i]=mx[v]+w;
        if(i<sz(child[u])-1) maxi(suf[i],suf[i+1]);
    }
    rep(i,sz(child[u])){
        int v=child[u][i].fi, w=child[u][i].se;
        out[v]=out[u]+w;
        if(i>0) maxi(out[v],pre[i-1]+w);
        if(i<sz(child[u])-1) maxi(out[v],suf[i+1]+w);
    }
    for(auto [v,w]:child[u]) reroot(v);
}

ll hi[3],res;
int solve(){
    memset(miDia,0x3f,sizeof(miDia));
    rep(i,n) if(!vis[i]){
        root[numRoot]=i;
        dfs(i);
        reroot(i);
        numRoot++;
    }

    rep(i,numRoot) maxi(res,mxDia[i]);

    memset(hi,-0x3f,sizeof(hi));
    rep(i,numRoot){
        maxi(hi[2],miDia[i]);
        if(hi[1]<hi[2]) swap(hi[1],hi[2]);
        if(hi[0]<hi[1]) swap(hi[0],hi[1]);
    }

    maxi(res, max(hi[0]+hi[1]+l,hi[1]+hi[2]+2*l));
    return res;
}

int travelTime(int NN, int MM, int LL, int AA[], int BB[], int TT[]){
    n=NN,m=MM,l=LL;
    rep(i,m){
        int u=AA[i],v=BB[i],t=TT[i];
        adj[u].eb(v,t);
        adj[v].eb(u,t);
    }
    return solve();
}

//int32_t main(){
//    #define task "test"
//    if(fopen(task".inp","r")){
//        freopen(task".inp","r",stdin);
//        freopen(task".out","w",stdout);
//    }
//    cin.tie(0)->sync_with_stdio(0);
//
//    int tc=1; //cin>>tc;
//    rep(i,tc){
//        solve();
//    }
//}

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