Submission #1029929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029929		vjudge1	Dreaming (IOI13_dreaming)	C++17	100 / 100	89 ms	21448 KiB

dreaming

#include "dreaming.h"

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
using pii=pair<int,int>;

const int lim=1e5+100;


int n,m;
int ans=0;
vector<pii>v[lim];
vector<int>results,curnodes;
bool done[lim];
int dist[lim],dp[lim],up[lim];

void dd(int node,int par,bool init){
    if(init)curnodes.pb(node);
    for(auto[j,c]:v[node]){
        if(j!=par){
            dist[j]=dist[node]+c;
            dd(j,node,init);
        }
    }
}

pair<pii,pii>bests[lim];

void ins(pair<pii,pii>&p,pii to){
    if(p.first.first<to.first)swap(to,p.first);
    if(p.second.first<to.first)p.second=to;
}

int dfs(int node,int par){
    dp[node]=0;
    for(auto[j,c]:v[node]){
        if(j==par)continue;
        dp[node]=max(dp[node],dfs(j,node)+c);
        ins(bests[node],{dp[j]+c,j});
    }
    return dp[node];
}

void dfs1(int node,int par){
    ins(bests[node],{up[node],-1});
    for(auto[j,c]:v[node]){
        if(j==par)continue;
        if(j^bests[node].first.second){
            up[j]=bests[node].first.first+c;
        }else{
            up[j]=bests[node].second.first+c;
        }
        dfs1(j,node);
    }
}


void process(int root){
    curnodes.clear();
    dist[root]=0;
    dd(root,-1,1);
    for(int i:curnodes){
        done[i]=1;
        if(dist[root]<dist[i]){
            root=i;
        }
    }
    if(!dist[root]){
        results.pb(0);
        return;
    }
    dist[root]=0;
    dd(root,-1,0);
    for(int i:curnodes){
        ans=max(ans,dist[i]);
    }
    dfs(root,-1);
    up[root]=0;
    dfs1(root,-1);
    int topush=INT_MAX;
    for(int i:curnodes){
        topush=min(topush,max({dp[i],up[i]}));
    }
    results.pb(topush);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    ans=0;
    n=N;
    m=M;
    results.clear();
    for(int i=0;i<n;i++){
        v[i].clear();
        done[i]=0;
        dist[i]=INT_MAX;
    }
    for(int i=0;i<m;i++){
        v[A[i]].pb({B[i],T[i]});
        v[B[i]].pb({A[i],T[i]});
    }
    for(int i=0;i<n;i++){
        if(!done[i]){
            process(i);
        }
    }
    sort(results.begin(),results.end());
    if(results.size()==2){
        ans=max(ans,results[0]+results[1]+L);
    }
    if(2<results.size()){
        ans=max(ans,results[results.size()-1]+results[results.size()-2]+L);
        ans=max(ans,results[results.size()-3]+results[results.size()-2]+2*L);
    }
    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