Submission #1007487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007487		Mardonbekhazratov	Dreaming (IOI13_dreaming)	C++17	100 / 100	56 ms	29184 KiB

dreaming

    #include "dreaming.h"
    #include<bits/stdc++.h>
     
    using namespace std;
     
    #define ll long long
     
    int n,m,l;
    vector<int>sz;
    vector<bool>vis;
    vector<vector<pair<int,int>>>v;
     
    int dfs(int x){
        vis[x]=true;
        sz[x]=0;
        for(auto [z,w]:v[x]){
            if(!vis[z]){
                sz[x]=max(sz[x],dfs(z)+w);
            }
        }
        return sz[x];
    }
     
    int mn,mx;
     
    void dfs2(int x,int y=0){
        vis[x]=true;
        multiset<int>s;
        s.insert(y);
        for(auto [z,w]:v[x]){
            if(!vis[z]){
                s.insert(sz[z]+w);
            }
        }
        mn=min(mn,*s.rbegin());
        for(auto [z,w]:v[x]){
            if(!vis[z]){
                s.erase(s.find(sz[z]+w));
                dfs2(z,*s.rbegin()+w);
                s.insert(sz[z]+w);
            }
        }
        int k=*s.rbegin();
        s.erase(s.find(*s.rbegin()));
        if(!s.empty()) k+=*s.rbegin();
        mx=max(mx,k);
    }
     
    int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
        n=N;
        m=M;
        l=L;
        v.assign(n,{});
        for(int i=0;i<m;i++){
            v[A[i]].push_back({B[i],T[i]});
            v[B[i]].push_back({A[i],T[i]});
        }
        sz.resize(n);
        vis.assign(n,false);
        for(int i=0;i<n;i++){
            if(!vis[i]){
                dfs(i);
            }
        }
        vector<int>a,diametres;
        vis.assign(n,false);
        for(int i=0;i<n;i++){
            if(!vis[i]){
                mx=0;
                mn=(int)1e9;
                dfs2(i);
                a.push_back(mn);
                diametres.push_back(mx);
            }
        }
        if(a.size()==1){
            return diametres[0];
        }
        sort(diametres.begin(),diametres.end());
        sort(a.begin(),a.end());
        int s=a.back()+a[a.size()-2]+l;
        if(a.size()>2) s=max(s,a[a.size()-2]+a[a.size()-3]+2*l);
        return max(diametres.back(),s);
    }

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