Submission #228425

#	Time	Username	Problem	Language	Result	Execution time	Memory
228425		mohamedsobhi777	Dreaming (IOI13_dreaming)	C++14	47 / 100	161 ms	32888 KiB

dreaming

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

using namespace std ; 

const int N = 1e5 + 7 ; 

int mn ; 
int vis[N] ; 
int mxx[N] ; 
int anss[N] ;  

vector<pair<int , int > > adj[N]; 
int node , dst ; 
int ansi , ans2;

int solve1(int x, int p){
    int ret = 0 ; 
    for(auto u : adj[x]){
        if(u.first==p)continue ; 
        int dfx = solve1(u.first , x) + u.second ; 
        ret = max(ret , dfx) ;
    }
    anss[x] = ret ; 
    return mxx[x] = ret ; 
}

void dfs(int x , int p , int h){
    for(auto u : adj[x]){
        if(u.first==p)continue ; 
        dfs(u.first , x , h + u.second) ; 
    }
    if( h > dst){
        node = x ; 
        dst = h ; 
    }
    ans2 = max(ans2 , h) ;
}

int dfs1(int x, int p , int dp = 0 ){
    vis[x] ++ ; 
    anss[x] = max(anss[x] , dp ) ;
    ansi = min(ansi , anss[x]) ; 
    vector<int> dps , pre , suf; 
    for(auto u : adj[x]){
        if(u.first == p)continue ; 
        dps.push_back(mxx[u.first] + u.second) ;
        int mx = pre.size() ? pre.back() : 0 ; 
        pre.push_back(max(mx , dps.back())) ; 
    }  
    suf.resize(pre.size()) ;
    if(suf.size())
    suf[suf.size()-1] = dps[suf.size()-1] ; 
    for(int i = suf.size() -2 ; i >=0 ;i --){
        suf[i] = max(dps[i] , suf[i+1]) ; 
    }
    int i = 0 ; 
    for(auto u : adj[x]){
        if(u.first==p)continue ;
        int subdp = 0 ;
        if(i) subdp = max(subdp , pre[i-1]) ; 
        if(i < suf.size() -1 ) subdp = max(subdp , suf[i+1]) ; 
        dfs1(u.first , x , max(dp , subdp) + u.second) ; 
        i++; 
    } 
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i  =0 ; i< M ;i++){
        adj[A[i] +1 ].push_back({B[i]+1 , T[i]}) ;
        adj[B[i]+1].push_back({A[i]+1 , T[i]}) ;
    }
    vector<int> v; 
    for(int i = 1; i <=N ; i++){
        if(vis[i])continue ; 
        ansi = 2e9 ; 
        dfs(i , i , 0) ; dst = 0 ; 
        dfs(node , node , 0) ; 
        solve1(i , i ) ; 
        dfs1(i , i) ;
        v.push_back(ansi) ; 
    }
    if(v.size() == 1)return ans2 ; 
    else if(v.size() ==2 )return max(v[0] + v[1]  + L , ans2) ; 

    int s = v.size() ; 
    int ans = 2e9 ; 
    sort(v.begin() , v.end()) ; 
    for(int i = 0 ; i < s ; i++){
        int cur = v[i] + v.back() ; 
        if( i < s -1){
            if( i == s-2){
                cur = max(cur , v.back() + v[s-3] + L) ; 
            }
            else cur = max(cur , v.back() + v[s-2] + L) ; 
        }
        ans = min(ans , cur) ; 
    }
    return max(ans + L  , ans2) ; 
}

Compilation message (stderr)

dreaming.cpp: In function 'int dfs1(int, int, int)':
dreaming.cpp:62:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i < suf.size() -1 ) subdp = max(subdp , suf[i+1]) ; 
            ~~^~~~~~~~~~~~~~~
dreaming.cpp:66:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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