Submission #453745

#	Time	Username	Problem	Language	Result	Execution time	Memory
453745		tht2005	Dreaming (IOI13_dreaming)	C++17	100 / 100	101 ms	16164 KiB

dreaming

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

#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define FORE(i,a) for(auto&i:a)
#define rep(i,a,b,z) for(int i=(a),_b=(b),_z=(z);i<=_b;i+=_z)
#define SZ(a) ((int)a.size())
#define ALL(a) a.begin(),a.end()

#define fs first
#define sc second
typedef pair<int,int> ii;
const int nmax=100010;

int f[nmax],f2[nmax],g[nmax],vst[nmax];
vector<ii>adj[nmax];

void dfs(int u, int p=-1)
{
    vst[u]=*vst;
    f[u]=f2[u]=0;
    FORE(x,adj[u]){
        if(x.sc==p)continue;
        dfs(x.sc,u);
        if(f[u]<f[x.sc]+x.fs){
            f2[u]=f[u];
            f[u]=f[x.sc]+x.fs;
        }
        else if(f2[u]<f[x.sc]+x.fs)
            f2[u]=f[x.sc]+x.fs;
    }
}

void dfs2(int u, int p=-1)
{
    FORE(x,adj[u]){
        if(x.sc==p)continue;
        if(f[u]==f[x.sc]+x.fs)g[x.sc]=max(g[u],f2[u])+x.fs;
        else g[x.sc]=max(g[u],f[u])+x.fs;
        dfs2(x.sc,u);
    }
}

int calc(int n, int l, vector<int>& a)
{
    if(n==1)return a[1];
    if(n==2)return a[1]+a[2]+l;
    sort(a.begin()+1,a.end(),greater<int>());
    return min({
        max({a[1]+a[2]+l,a[1]+a[3]+l,a[2]+a[3]+l+l}),
        max({a[2]+a[1]+l,a[2]+a[3]+l,a[1]+a[3]+l+l}),
        max({a[3]+a[1]+l,a[3]+a[2]+l,a[1]+a[2]+l+l})
    });
}

int travelTime(int N,int M,int L,int A[],int B[],int T[])
{
    FOR(i,0,M-1){
        ++A[i],++B[i];
        adj[A[i]].push_back({T[i],B[i]});
        adj[B[i]].push_back({T[i],A[i]});
    }
    FOR(i,1,N)if(!vst[i])++*vst,dfs(i),dfs2(i);
    FOR(i,1,N)f[i]=max(f[i],g[i]);
    vector<int>a(*vst+1,0x3f3f3f3f);
    FOR(i,1,N)a[vst[i]]=min(a[vst[i]],f[i]);
    f[0]=calc(*vst,L,a);
    return *max_element(f,f+1+N);
}

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