Submission #948454

#	Time	Username	Problem	Language	Result	Execution time	Memory
948454		irmuun	Dreaming (IOI13_dreaming)	C++17	100 / 100	64 ms	15048 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int maxn=1e5+5;

vector<pair<int,int>>adj[maxn];
vector<int>d(maxn),ver;
vector<bool>used(maxn);
int dist,mx,vr[3];

void dfs(int x,int p,int e){
    used[x]=true;
    if(e==0){
        ver.pb(x);
    }
    if(dist>mx){
        mx=dist;
        vr[e]=x;
    }
    for(auto [y,w]:adj[x]){
        if(y!=p){
            dist+=w;
            dfs(y,x,e);
            dist-=w;
        }
    }
}
void calc(int x,int p){
    d[x]=max(d[x],dist);
    mx=max(mx,dist);
    for(auto [y,w]:adj[x]){
        if(y!=p){
            dist+=w;
            calc(y,x);
            dist-=w;
        }
    }
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(int i=0;i<M;i++){
        adj[A[i]].pb({B[i],T[i]});
        adj[B[i]].pb({A[i],T[i]});
    }
    vector<int>v,u;
    for(int i=0;i<N;i++){
        if(!used[i]){
            ver.clear();
            mx=-1,dist=0;
            dfs(i,-1,0);
            mx=-1,dist=0;
            dfs(vr[0],-1,1);
            mx=0,dist=0;
            calc(vr[0],-1);
            mx=0,dist=0;
            calc(vr[1],-1);
            v.pb(mx);
            int mn=1e9;
            for(auto j:ver){
                mn=min(mn,d[j]);
            }
            u.pb(mn);
        }
    }
    if(v.size()==1){
        return v[0];
    }
    if(v.size()==2){
        return max({v[0],v[1],u[0]+u[1]+L});
    }
    int D=0,ans=1e9;
    for(auto x:v){
        D=max(D,x);
    }
    multiset<int,greater<int>>st;
    for(auto x:u){
        st.insert(x);
    }
    for(auto x:u){
        st.erase(st.find(x));
        auto it=st.begin();
        it++;
        ans=min(ans,max(x+*st.begin()+L,*st.begin()+*it+2*L));
        st.insert(x);
    }
    ans=max(ans,D);
    return ans;
}

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