Submission #128954

#	Time	Username	Problem	Language	Result	Execution time	Memory
128954		youssefbou62	Dreaming (IOI13_dreaming)	C++14	0 / 100	1078 ms	12920 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 ,a,b ;
        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 v; 
            visited[u] = 1 ; 
            color[u] = c ; 
            for(pi pr : adj[u] ){
                v = pr.fi  ; 
                if( !visited[v]) {
                    dfs4(v); 
                }
            }
        }
        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]) ; 
            
            } 
            for(int i = 0 ; i < N ; i++ ){
                if(!visited[i]){
                dfs4(i) ; 
                c++ ; 
                }
                Min[i]=1e9; 
            }
            int ans = 0 ; 
            for(int i = 0 ; i < N ; i++ ){
                Max = 0 ;  dfs3(i,-1,0) ; 
                ans = max (Max,ans) ; 
                Min[color[i]] =min( Min[color[i]] , Max ); 
            }
            
            for(int i = 0 ; i < c ; i++ ){
                if( Min[i]!= 1e9 ){
                max2(a,b,Min[i]) ; 
                }
            }
            // cout << Min[0]<<" " <<Min[1] << endl ; 
            // cout << a << " " << b << endl;

            if( N == 1 )return a; 
            ans = max ( ans , a + b + L ) ; 
            return ans ; 
        }




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