Submission #441294

#	Time	Username	Problem	Language	Result	Execution time	Memory
441294		julian33	Dreaming (IOI13_dreaming)	C++14	100 / 100	139 ms	16264 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
 
using namespace std;
 
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr<<vars<<" = ";
    string delim="";
    (...,(cerr<<delim<<values,delim=", "));
    cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
 
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
 
const int mxN=1e5+5;
 
vector<pii> graph[mxN];
ll dist[mxN],r=2e9,nd;
int ep,seen[mxN],good[mxN],st;
 
void dfs(int at,int p){
    seen[at]=1;
    if(dist[at]>=dist[ep])
        ep=at;
    for(pii &i:graph[at]){
        if(i.first!=p){
            dist[i.first]=dist[at]+i.second;
            dfs(i.first,at);
        }
    }
}
 
void get_rad(int at,int p){
    if(at==ep)
        good[at]=1;
    for(pii &i:graph[at]){
        if(i.first==p)
            continue;
        get_rad(i.first,at);
        good[at]|=good[i.first];
    }
    if(good[at]){
        if(max(dist[at],dist[ep]-dist[at])<r){
            r=max(dist[at],dist[ep]-dist[at]);
            nd=at;
        }
    }
}
 
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(int i=0;i<M;i++){
        graph[A[i]].pb({B[i],T[i]});
        graph[B[i]].pb({A[i],T[i]});
    }
    vector<pii> mids;
    for(int i=0;i<N;i++){
        if(seen[i])
            continue;
        ep=N;
        dfs(i,-1);
        dist[ep]=0; st=ep;
        dfs(ep,-1);
        r=2e9;
        get_rad(st,-1);
        mids.pb({r,nd});
    }
    sort(mids.rbegin(),mids.rend());
    for(int i=1;i<sz(mids);i++){
        graph[mids[0].second].pb({mids[i].second,L});
        graph[mids[i].second].pb({mids[0].second,L});
    }
    dfs(0,-1); dist[ep]=0;
    dfs(ep,-1); 
    return dist[ep];
}

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