oj.uz

Submission #228408

# Submission time Handle Problem Language Result Execution time Memory
228408 2020-05-01T00:43:13 Z mohamedsobhi777 Dreaming (IOI13_dreaming) C++14
0 / 100
 66 ms 15480 KB 
#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 ; 
        anss[x] = max(anss[x] , ret + dfx ); 
        ret = max(ret , dfx) ;
    }
    anss[x] = ret ; 
    return mxx[x] = ret ; 
}

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

int dfs1(int x, int p , int dp = 0 ){
    vis[x] ++ ; 

    anss[x] = max(anss[x] , dp ) ;
    ansi = min(ansi , anss[x]) ; 

    for(auto u : adj[x]){
        if(u.first==p)continue ;
        int subdp = 0 ;
        for(auto j : adj[x]){
            if(j.first == p || j == u){
                continue ; 
            }
            subdp = max(subdp , mxx[j.first] + j.second) ; 
        } 
        dfs1(u.first , x , max(dp , subdp) + u.second) ; 
    }
}

int pre[N] , suf[N] ; 

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; 
    multiset<int> mul ; 
    for(int i = 2; i <= N && !vis[i] ; i++){
        ansi = 2e9 ; 
        dfs(i , i , 0) ; 
        dst = 0 ; 
        dfs(node , node , 0) ; 
        ans2 = max(ans2 , dst) ; 
        solve1(i , i ) ; 
        dfs1(i , i) ;
        v.push_back(ansi) ; 
        mul.insert(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 ; 

    for(auto u : v){
        mul.erase(mul.find(u)) ; 
        int mx1 = -1 , mx2 = -1 ; 
        auto e = mul.end() ;
        e-- ; mx1 = *e ; 
        e-- ; mx2 = *e ;
        int now = max(u + mx1 + L , mx1 + mx2 + L + L ) ; 
        ans = min(ans , now ) ;
        mul.insert(u) ; 
    }   
    return max(ans , dst) ; 
}

Compilation message

dreaming.cpp: In function 'int dfs1(int, int, int)':
dreaming.cpp:59:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:84:9: warning: unused variable 's' [-Wunused-variable]
     int s = v.size() ; 
         ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 13176 KB Output is correct
2 Correct 66 ms 15480 KB Output is correct
3 Correct 42 ms 9848 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 12 ms 3584 KB Output is correct
6 Correct 20 ms 5504 KB Output is correct
7 Incorrect 6 ms 2816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 13176 KB Output is correct
2 Correct 66 ms 15480 KB Output is correct
3 Correct 42 ms 9848 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 12 ms 3584 KB Output is correct
6 Correct 20 ms 5504 KB Output is correct
7 Incorrect 6 ms 2816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 13176 KB Output is correct
2 Correct 66 ms 15480 KB Output is correct
3 Correct 42 ms 9848 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 12 ms 3584 KB Output is correct
6 Correct 20 ms 5504 KB Output is correct
7 Incorrect 6 ms 2816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 6016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 13176 KB Output is correct
2 Correct 66 ms 15480 KB Output is correct
3 Correct 42 ms 9848 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 12 ms 3584 KB Output is correct
6 Correct 20 ms 5504 KB Output is correct
7 Incorrect 6 ms 2816 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 13176 KB Output is correct
2 Correct 66 ms 15480 KB Output is correct
3 Correct 42 ms 9848 KB Output is correct
4 Correct 13 ms 4224 KB Output is correct
5 Correct 12 ms 3584 KB Output is correct
6 Correct 20 ms 5504 KB Output is correct
7 Incorrect 6 ms 2816 KB Output isn't correct
8 Halted 0 ms 0 KB -