oj.uz

Submission #128753

# Submission time Handle Problem Language Result Execution time Memory
128753 2019-07-11T09:02:58 Z youssefbou62 Dreaming (IOI13_dreaming) C++14
0 / 100
 60 ms 7024 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] , color[NN]; 
    bool visited[NN] ;
    int Min[NN], Max, c  ;
    void dfs3(int u , int p , int d ){
        int v , w;
        Max = max ( Max , d ) ;  
        for(pi pr : adj[u] ){
            v = pr.fi  ; 
            w = pr.se ; 
            if( v!= p){
                dfs3(v,u,d+w); 
            }
        }

    }

    void dfs4(int u , int p ){
        int v; 
        visited[u] = 1 ; 
        color[u] = c ; 
        for(pi pr : adj[u] ){
            v = pr.fi  ; 
            if( v!= p){
                dfs4(v,u); 
            }
        }
    }
    // 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){
    //                 dp1[v] = max(dp1[u]+w,dp1[v]) ; 
    //             }if( dp1[u] != dp2[v]+w){
    //                 dp2[v] = max(dp1[u]+w,dp2[v]) ;
    //             }    
                
    //             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[]){
        vector<int> ans ; 
        for(int i = 0 ; i < M ; i++ ){
            edge(A[i],B[i],T[i]) ; 
            edge(B[i],A[i],T[i]) ; 
            ans.pb(T[i]) ; 
        }
        sort(all(ans)) ; 
        // for(int i = 0 ; i < N ; i++ ){
        //     dfs4(i,-1) ; 
        //     c++ ; 
        //     Min[i]=1e9; 
        // }
        // for(int i = 0 ; i < N ; i++ ){
        //     Max = 0 ; 
        //     dfs3(i,-1,0) ; 
        //     Min[color[i]] =min( Min[color[i]] , Max ); 
        // }
        // vector<int> ans ; 
        // for(int i = 0 ; i < N ; i++ ){
        //     if( Min[i]!= 1e9 )
        //     ans.pb(Min[i]); 
        // }
        // sort(all(ans)) ; 
        int ans1 = 0 , a = 0 , b = 0 , c = 0 ;  
        // // cout << ans.back() << endl; 
        if( !ans.empty() ){
            a = ans.back() ; 
            ans.pop_back(); 
        }if( !ans.empty() ){
            b = ans.back() ; 
            ans.pop_back(); 
        }if( !ans.empty() ){
            c = ans.back() ; 
            ans.pop_back(); 
        }

        return max ( L*2 + b + c , L + a + b )  ; 
        
    }




    // int main(){
    //     ifstream cin("in.in"); 
    //     int n,m,l;
    //     cin >>n>>m >>l; 
    //     int a[m],b[m],t[m] ;
    //     for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>t[i] ;     
    //     cout <<  travelTime(n,m,l,a,b,t) << endl;
    // }

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:122:13: warning: unused variable 'ans1' [-Wunused-variable]
         int ans1 = 0 , a = 0 , b = 0 , c = 0 ;  
             ^~~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 5112 KB Output is correct
2 Correct 25 ms 5112 KB Output is correct
3 Correct 25 ms 5580 KB Output is correct
4 Correct 25 ms 5624 KB Output is correct
5 Correct 25 ms 5624 KB Output is correct
6 Correct 27 ms 5880 KB Output is correct
7 Correct 26 ms 5752 KB Output is correct
8 Correct 25 ms 5496 KB Output is correct
9 Correct 24 ms 5496 KB Output is correct
10 Correct 25 ms 5624 KB Output is correct
11 Correct 4 ms 2680 KB Output is correct
12 Correct 4 ms 2680 KB Output is correct
13 Correct 4 ms 2680 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 5 ms 2856 KB Output is correct
16 Correct 4 ms 2680 KB Output is correct
17 Correct 4 ms 2680 KB Output is correct
18 Correct 4 ms 2812 KB Output is correct
19 Correct 4 ms 2680 KB Output is correct
20 Incorrect 5 ms 2680 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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