Submission #131109

#	Time	Username	Problem	Language	Result	Execution time	Memory
131109		youssefbou62	Dreaming (IOI13_dreaming)	C++14	100 / 100	229 ms	22392 KiB

dreaming

	#include <bits/stdc++.h>
       #include <dreaming.h>
        using namespace std;
		// #pragma GCC target ("avx2")
		// #pragma GCC optimization ("O3")
		// #pragma GCC optimization ("unroll-loops")
        #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 ; 
        vector<pll> adj[NN] ; 
        ll dp1[NN],dp2 [NN] , chil[NN] , chil1[NN], pass[NN] ,ans , ans1 ; 

        void dfs0(int u , int p ){
        	pass[u]=1; 
       		int v ; ll w ; 
       		// cout << "dfs0"<<endl; 
       		for(pi pr : adj[u]){
       			v = pr.fi ; 
       			w = pr.se ; 
       			if( p != v ){
       				dfs0(v,u) ;
       				if( dp1[v] + w > dp1[u]){
       					dp1[u] = dp1[v] + w ; 
       					chil[u] = v ; 
       				}
       			}
       		}
        }

        void dfs1(int u , int p ){
        	int v ; ll w ;
        	pass[u]=2;  
        	// cout << "dfs1"<<endl; 
       		for(pi pr : adj[u]){
       			v = pr.fi ; 
       			w = pr.se ; 
       			if(p!=v)
       			dfs1(v,u); 
       			if( p != v && v != chil[u] ){
       				if( dp1[v]+w > dp2[u] ){
       					chil1[u] = v ; 
       					dp2[u] = dp1[v]+w  ; 
       				}
       			}
       		}
        }

        void dfs2(int u , int p ){
        	int v ; ll w ;
        	pass[u]=3;  
        	// cout << "dfs2"<<endl; 
       		for(pi pr : adj[u]){
       			v = pr.fi ; 
       			w = pr.se ; 
       			if( v != p && v != chil[u] ){
       				if( dp1[u] + w > dp1[v] ){
       					dp2[v] = dp1[v] ; 
       					chil1[v] = chil[v] ; 
       					dp1[v] = dp1[u] + w; 
       					chil[v] = u ; 
       				}else if( dp1[u] + w > dp2[v]){
       					dp2[v] = dp1[u] + w;  
       					chil1[v] = u ; 
       				}
       			}else if( v != p && v != chil1[u]){
       				if( dp2[u] + w > dp1[v] ){
       					dp2[v] = dp1[v] ; 
       					dp1[v] = dp2[u] + w;
       					chil1[v] = chil[v] ; 
       					chil[v] = u ;  
       				}else if( dp2[u] + w > dp2[v]){
       					dp2[v] = dp2[u] + w; 
       					chil1[v] = u ; 
       				}
       			
       			}
       			if( v!= p )
       				dfs2(v,u) ; 
       		}

        }

        void dfs4(int u , int p , ll& Min ){
        	pass[u]=4; 
        	Min = min(Min,dp1[u]);  
        	ans1 = max(ans1,dp1[u]); 
        	for(pi v : adj[u]){
        		if(v.fi!=p){
        			dfs4(v.fi,u,Min); 
        		}
        	}
    	}
        void edge(int u , int v , int w ){
            adj[u].pb({v,1LL*w}) ; 
        }
        int travelTime(int N,int M,int L ,int A[],int B[],int T[]){
            // cout <<"x"<<endl; 
            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( pass[i] == 0 ) dfs0(i,-1) ; 
        	for(int i = 0 ; i < N ; i++ )if( pass[i] == 1 ) dfs1(i,-1) ; 
        	for(int i = 0 ; i < N ; i++ )if( pass[i] == 2 ) dfs2(i,-1) ;  
        	ll Min ; 
        	vector<ll> longest_paths; 
        	for(int i = 0 ; i < N ; i++ ){
        		Min = 1e18; 
        		if( pass[i] == 3 ){
        			dfs4(i,-1,Min);
        			longest_paths.pb(Min);

        		}
        	}
        	sort(all(longest_paths)); 
        	reverse(all(longest_paths)) ;
        	ans = 0; 
        	// if( N == 2 )return L ; 
        	// if( N == 1 )
        	// cout << "L "<<	L << endl; 
        	// for(int p : longest_paths)cout << p << " "; 
        	if( longest_paths.size() > 1 ){
        		ans = max(ans,L+longest_paths[0]+longest_paths[1]); 
        		
        		if( longest_paths.size() > 2 ){
        			ans = max(ans,2*L+longest_paths[1]+longest_paths[2]); 
        		}
        	}

        	ans = max  (ans,ans1); 
        	// if( ans == 631 )return L; 

        	return ans ; 
        }




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

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