oj.uz

Submission #128550

# Submission time Handle Problem Language Result Execution time Memory
128550 2019-07-11T06:15:58 Z youssefbou62 Dreaming (IOI13_dreaming) C++14
0 / 100
 67 ms 12664 KB 
#include <bits/stdc++.h>
#include <dreaming.h>
using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll ;
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef priority_queue< int, vector <int> , greater<int> > spq;
const int NN = 1e5+5 ; 
vpi adj[NN] ; 
int dp1[NN],dp2 [NN] ; 
bool visited[NN] ;
int Min ;

void max2(int& a , int& b , int x ){
    if( x < b) return ; 
    if( x > a ){
        b = a ; 
        a = x ; 
        return ;
    }    
    if( x > b && x < a ){
        b = x ; 
    }
}
void dfs(int u , int p){
    int v , w; 
    visited[u] = 1 ; 
    for(pi pr : adj[u] ){
        v = pr.fi  ; 
        w = pr.se ; 
        if( v != p ){
        dfs(v,u) ;
        max2(dp1[u],dp2[u],w+dp1[v]);  
        } 
    }
}
void dfs0(int u , int p ){
    // cout << u << " " << dp1[u] << " " << dp2[u]<<endl ; 
    for(pi v : adj[u]){
        if( v.fi != p )
            dfs0(v.fi,u) ; 
    }
}

void dfs1(int u , int p ){
    int w , v ; 
    for(pi pr : adj[u] ){
        v = pr.fi  ; 
        w = pr.se ; 
        if( v != p ){
            if( dp1[u] != dp1[v]+w){
                max2(dp1[v],dp2[v],dp1[u]+w ); 
            }else if( dp2[u] != dp2[v]+w) {
                max2(dp1[v],dp2[v],dp2[u]+w );
            }
            dfs1(v,u) ; 
        }
    }
    Min = min(Min,dp1[u]) ; 
}
void edge(int u , int v , int w ){
    adj[u].pb({v,w}) ; 
}
int travelTime(int N,int M,int L ,int A[],int B[],int T[]){
    
    for(int i = 0 ; i < M ; i++ ){
        edge(A[i],B[i],T[i]) ; 
        edge(B[i],A[i],T[i]) ; 
    }
    priority_queue<int> q; 
    for(int i = 0 ; i < N ; i++ ){
        if( !visited[i]){
            Min= 1e9 ; 
            dfs(i,-1);
            dfs1(i,-1); 
            dfs0(i,-1) ;  
            q.push(Min) ; 
        }
    }
    Min = q.top() ; q.pop() ; 
    return L+Min+q.top();   
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6648 KB Output is correct
2 Incorrect 28 ms 6648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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