Submission #409225

#	Time	Username	Problem	Language	Result	Execution time	Memory
409225		pliam	Dreaming (IOI13_dreaming)	C++14	100 / 100	125 ms	21540 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define MAXN 100005
#define INF (ll)1e9+5
using namespace std;
typedef long long ll;

vector<pair<int,ll>> adj[MAXN];//(to,weight)
ll dp_down1[MAXN],dp_down2[MAXN],dp_d[MAXN],dp_up[MAXN],ans[MAXN];
bool visited[MAXN];
ll min_len,id_min;
vector<pair<ll,int>> rep;//(weight,id)
int n;
ll res;

void dfs1(int curr,int par=-1){
    visited[curr]=true;
    for(auto p:adj[curr]){
        int to = p.first;
        ll w = p.second;
        if(to==par) continue;
        dfs1(to,curr);
        if(dp_down1[to]+w>dp_down1[curr]){
            dp_down1[curr]=dp_down1[to]+w;
            dp_d[curr]=to;
        }
    }
    for(auto p:adj[curr]){
        int to = p.first;
        ll w = p.second;
        if(to==par||to==dp_d[curr]) continue;
        if(dp_down1[to]+w>dp_down2[curr]){
            dp_down2[curr]=dp_down1[to]+w;
        }
    }
}

void dfs2(int curr,int par=-1,int wpar=0){
    if(par!=-1){
        if(dp_d[par]!=curr) dp_up[curr]=max(dp_up[par],dp_down1[par])+wpar;
        else dp_up[curr]=max(dp_up[par],dp_down2[par])+wpar;
    }
    ans[curr]=max(dp_up[curr],dp_down1[curr]);
    if(ans[curr]<min_len){
        min_len=ans[curr];
        id_min=curr;
    }
    res=max(res,ans[curr]);
    for(auto p:adj[curr]){
        int to = p.first;
        ll w = p.second;
        if(to==par) continue;
        dfs2(to,curr,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]].push_back({B[i],T[i]});
        adj[B[i]].push_back({A[i],T[i]});
    }
    for(int i=0;i<N;i++){
        if(!visited[i]){
            min_len=INF;
            dfs1(i);
            dfs2(i);
            rep.push_back({min_len,id_min});
        }
    }
    sort(rep.begin(),rep.end());
    int rsize=rep.size();
    if(rsize==1){
        return res;
    }else if(rsize==2){
        return max(rep[rsize-1].first+rep[rsize-2].first+L,res);
    }else{
        return max({rep[rsize-1].first+rep[rsize-2].first+L,rep[rsize-2].first+rep[rsize-3].first+2*L,res});
    }
}

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