제출 #881235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
881235		AlphaMale06	Dreaming (IOI13_dreaming)	C++14	100 / 100	98 ms	16256 KiB

dreaming

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

#define pb push_back
#define F first
#define S second




const int N = 1e5+5;
bool mark[N];
int dist[N][2];
vector<pair<int, int>> adj[N];
int mxdep, endnd;
int dst, diam;

void dfs(int node, vector<int>& comp){
    comp.pb(node);
    mark[node]=1;
    for(auto to : adj[node]){
        if(!mark[to.F])dfs(to.F, comp);
    }
}

void dfs(int node, int dep){
    if(dep>mxdep){
        endnd=node;
        mxdep=dep;
    }
    mark[node]=1;
    for(auto to : adj[node]){
        if(!mark[to.F])dfs(to.F, dep+to.S);
    }
}
void dfs(int node, int dep, int t){
    dist[node][t]=dep;
    mark[node]=1;
    for(auto to : adj[node]){
        if(!mark[to.F])dfs(to.F, dep+to.S, t);
    }
}


void finddiameter(int node){
    vector<int> comp;
    dfs(node, comp);
    for(int e : comp)mark[e]=0;
    mxdep=0;
    int strt=node;
    dfs(strt, 0);
    strt=endnd;
    for(int e : comp)mark[e]=0;
    mxdep=0;
    dfs(strt, 0);
    for(int e : comp)mark[e]=0;
    diam=mxdep;
    dfs(strt, 0, 0);
    for(int e : comp)mark[e]=0;
    dfs(endnd, 0, 1);
    dst=1e9;
    for(int e : comp){
        dst=min(dst, max(dist[e][0], dist[e][1]));
    }
}

int travelTime(int n, int m, int L, int a[], int b[], int c[]) {
    for(int i=0; i< m; i++){
        adj[a[i]].pb({b[i], c[i]});
        adj[b[i]].pb({a[i], c[i]});
    }
    vector<int>dsts;
    vector<int>diams;
    for(int i=0; i< n; i++){
        if(!mark[i]){
            finddiameter(i);
            dsts.pb(dst);
            diams.pb(diam);
        }
    }
    int ret=0;
    for(int e : diams){
        ret=max(ret, e);
    }
    sort(dsts.begin(), dsts.end());
    int sz=dsts.size();
    if(sz==1)return ret;
    else if(sz==2)return max(ret, L+dsts[1]+dsts[0]);
    else return max({ret, L+dsts[sz-1]+dsts[sz-2], 2*L+dsts[sz-2]+dsts[sz-3]});
}

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