Submission #128656

#	Time	Username	Problem	Language	Result	Execution time	Memory
128656		youssefbou62	Dreaming (IOI13_dreaming)	C++14	0 / 100	1070 ms	11332 KiB

dreaming

    #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[]){
        
        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 ; 
        //         Max = 0 ; 
        //         dfs(i,-1);
        //         dfs1(i,-1); 
        //         dfs0(i,-1) ;  
        //         q.push(Max) ; 
        //     }
        // 
        for(int i = 0 ; i < N ; i++ )if(!visited[i])dfs4(i,-1) , c++ ,  Min[color[i]]=1e9; 
        for(int i = 0 ; i < N ; i++ ){
            Max = 0 ; 
            dfs3(i,-1,0) ; 
            Min[color[i]] = min( 
            Min[color[i]] , Max); 
         }
         for(int i = 0 ; i < N ; i++ )q.push(Min[i]) ; 
        Max = q.top() ; q.pop() ; 
        return L + q.top() + Max ; 
    }

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