제출 #900622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
900622		JakobZorz	꿈 (IOI13_dreaming)	C++17	100 / 100	58 ms	18156 KiB

dreaming

#include"dreaming.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;

vector<pair<int,int>>nodes[100000];
bool vis[100000];
int par[100000];
int biggest_depth[100000];
int biggest_len_up[100000];
vector<int>nodes_list;

void dfs(int node){
    if(vis[node])
        return;
    vis[node]=true;
    nodes_list.push_back(node);
    for(auto ne:nodes[node]){
        if(vis[ne.first])
            par[node]=ne.first;
        else{
            dfs(ne.first);
            biggest_depth[node]=max(biggest_depth[node],biggest_depth[ne.first]+ne.second);
        }
    }
}

void dfs2(int node){
    pair<int,int>deepest1,deepest2;
    for(auto ne:nodes[node]){
        if(ne.first==par[node])
            continue;
        
        int depth=biggest_depth[ne.first]+ne.second;
        if(depth>=deepest1.first){
            deepest2=deepest1;
            deepest1={depth,ne.first};
        }else if(depth>deepest2.first){
            deepest2={depth,ne.first};
        }
    }
    
    for(auto ne:nodes[node]){
        if(ne.first==par[node])
            continue;
        
        if(ne.first==deepest1.second){
            biggest_len_up[ne.first]=max(biggest_len_up[node],deepest2.first)+ne.second;
        }else{
            biggest_len_up[ne.first]=max(biggest_len_up[node],deepest1.first)+ne.second;
        }
        
        dfs2(ne.first);
    }
}

pair<int,int>get_diameter(int root){
    nodes_list.clear();
    par[root]=-1;
    dfs(root);
    dfs2(root);
    
    int res=1e9,diam=0;
    
    for(int node:nodes_list){
        diam=max(diam,biggest_depth[node]+biggest_len_up[node]);
        res=min(res,max(biggest_depth[node],biggest_len_up[node]));
    }
    
    return {res,diam};
}

int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(int i=0;i<M;i++){
        nodes[A[i]].emplace_back(B[i],T[i]);
        nodes[B[i]].emplace_back(A[i],T[i]);
    }
    
    vector<int>dists;
    int diam=0;
    for(int i=0;i<N;i++)
        if(!vis[i]){
            auto r=get_diameter(i);
            dists.push_back(r.first);
            diam=max(diam,r.second);
        }
    
    sort(dists.begin(),dists.end());
    reverse(dists.begin(),dists.end());
    if(dists.size()==1)
        return max(dists[0],diam);
    else if(dists.size()==2)
        return max(dists[0]+dists[1]+L,diam);
    else
        return max(max(dists[0]+dists[1]+L,dists[1]+dists[2]+2*L),diam);
}

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