Submission #729540

#	Time	Username	Problem	Language	Result	Execution time	Memory
729540		Jean7	Dreaming (IOI13_dreaming)	C++14	100 / 100	112 ms	17088 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std ;

const int L = 24 ;
const int N = 1e5+5 ;
const int O = 2e9 ;

bool vs[N] ;
vector <int> v , ans ;
vector <pair<int,int>> g[N] ;

pair <int,int> dfs ( int i , int l ) {
    vs[i] = 1 ;
    pair <int,int> ret = {0,i} ;
    for ( auto it : g[i] ) {
        if ( it.first != l ) {
            pair <int,int> p = dfs ( it.first , i ) ;
            p.first += it.second ;
            if ( p.first > ret.first ) {
                ret = p ;
            }
        }
    }
    return ret ;
}

bool path ( int i , int l , int j ) {
    if ( i == j ) {
        return 1 ;
    }
    for ( auto it : g[i] ) {
        if ( it.first != l ) {
            if ( path ( it.first , i , j ) ) {
                v.push_back(it.second) ;
                return 1 ;
            }
        }
    }
    return 0 ;
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
    for ( int i = 0 ; i < m ; i++ ) {
        g[A[i]+1].push_back({B[i]+1,T[i]}) ;
        g[B[i]+1].push_back({A[i]+1,T[i]}) ;
    }
    int jean = 0 ;
    for ( int i = 1 ; i <= n ; i++ ) {
        if ( vs[i] ) {
            continue ;
        }
        int a = dfs ( i , 0 ).second ;
        int b = dfs ( a , 0 ).second ;
        path ( a , 0 , b ) ;
        int x = 0 ;
        for ( auto it : v ) {
            x += it ;
        }
        jean = max ( jean , x ) ;
        int cur = x , sum = 0 ;
        for ( auto it : v ) {
            sum += it ;
            cur = min ( cur , max ( sum , x - sum ) ) ;
        }
        reverse ( v.begin() , v.end() ) ;
        sum = 0 ;
        for ( auto it : v ) {
            sum += it ;
            cur = min ( cur , max ( sum , x - sum ) ) ;
        }
        ans.push_back(cur) ;
        v.clear() ;
    }
    sort ( ans.begin() , ans.end() , greater <int> () ) ;
    if ( ans.size() > 1 ) {
        jean = max ( jean , ans[0] + ans[1] + l ) ;
    }
    if ( ans.size() > 2 ) {
        jean = max ( jean , ans[1] + ans[2] + l + l ) ;
    }
    return jean ;
}

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