Submission #345084

#	Time	Username	Problem	Language	Result	Execution time	Memory
345084		rrrr10000	Dreaming (IOI13_dreaming)	C++14	100 / 100	148 ms	29036 KiB

dreaming

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n)  for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define rsort(a) {sort(all(a));reverse(all(a));}
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),(k))-v.begin())
#define fi first
#define se second
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define dame(a) {cout<<a<<endl;return 0;}
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
using vp=vector<P>;
using vvp=vector<vp>;
using vvvp=vector<vvp>;
using vb=vector<bool>;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outvvp(T v){rep(i,v.size())outvp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll inf=1001001001001001001;
#include "dreaming.h"
int travelTime(int n,int m,int L,int a[],int b[],int t[]){
    vvp g(n);
    rep(i,m){
        g[a[i]].pb(b[i],t[i]);
        g[b[i]].pb(a[i],t[i]);
    }
    vb visited(n,false);
    vi u(n),d(n);
    function<void(ll,ll)> dfs=[&](ll i,ll p){
        visited[i]=true;
        for(auto x:g[i])if(x.fi!=p){
            dfs(x.fi,i);
            chmax(d[i],d[x.fi]+x.se);
        }
    };
    ll mi;
    function<void(ll,ll)> dfs2=[&](ll i,ll p){
        vi ma;
        for(auto x:g[i])if(x.fi!=p)ma.pb(d[x.fi]+x.se);
        if(ma.size()){
            vi l(ma.size()),r(ma.size());
            l[0]=0;
            REP(i,1,l.size())l[i]=max(l[i-1],ma[i-1]);
            r.back()=0;for(ll i=r.size()-1;i>0;i--)r[i-1]=max(r[i],ma[i]);
            ll c=0;
            for(auto x:g[i])if(x.fi!=p){
                u[x.fi]=u[i]+x.se;
                chmax(u[x.fi],max(l[c],r[c])+x.se);
                c++;
            }
        }
        for(auto x:g[i])if(x.fi!=p)dfs2(x.fi,i);
        chmin(mi,max(u[i],d[i]));
    };
    vi v;
    rep(i,n)if(!visited[i]){
        mi=inf;dfs(i,-1);
        dfs2(i,-1);
        v.pb(mi);
    }
    rsort(v);
    ll ans=0;rep(i,n)chmax(ans,max(d[i],u[i]));
    if(v.size()>=2)chmax(ans,v[0]+v[1]+L);
    if(v.size()>=3)chmax(ans,v[1]+v[2]+L*2);
    return (int)(ans);
}/*
int main(){
    int a[10],b[10],t[10];
    int n,m,l;cin>>n>>m>>l;
    rep(i,m)cin>>a[i]>>b[i]>>t[i];
    out(travelTime(n,m,l,a,b,t));
}*/

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