Submission #128601

#	Time	Username	Problem	Language	Result	Execution time	Memory
128601		youssefbou62	꿈 (IOI13_dreaming)	C++14	0 / 100	99 ms	11384 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] ; 
    bool visited[NN] ;
    int Min ;

    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){
                    max2(dp1[v],dp2[v],dp1[u]+w ); 
                }
                else if( dp2[u] != dp1[v]+w) {
                 max2(dp1[v],dp2[v],dp2[u]+w );
                }
                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 ; 
                dfs(i,-1);
                dfs1(i,-1); 
                dfs0(i,-1) ;  
                q.push(Min) ; 
            }
        }
        Min = q.top() ; q.pop() ; 
        // cout << Min << " " << q.top() << endl; 
        return L+Min+q.top();   
    }
    // 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