Submission #128772

#	Time	Username	Problem	Language	Result	Execution time	Memory
128772		youssefbou62	Dreaming (IOI13_dreaming)	C++14	0 / 100	1083 ms	11740 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[]){
        vector<int> ans ; 
        for(int i = 0 ; i < M ; i++ ){
            edge(A[i],B[i],T[i]) ; 
            edge(B[i],A[i],T[i]) ; 
        
        } 
        for(int i = 0 ; i < N ; i++ ){
            if(!visited[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 ); 
        }
        for(int i = 0 ; i < N ; i++ ){
            if( Min[i]!= 1e9 )
            ans.pb(Min[i]); 
        }
        sort(all(ans)) ; 
        int ans1= 0 ; 
        if(!ans.empty())ans1+=ans.back() , ans.pop_back() ;
        if( N == 1 )return ans1; 
        if(!ans.empty())ans1+=ans.back() , ans.pop_back() ;
        // cout << 
        return (ans1+L) ; 
    }




    // 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;
    // }

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