제출 #888007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888007		TahirAliyev	Dreaming (IOI13_dreaming)	C++17	100 / 100	57 ms	17012 KiB

dreaming

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

using namespace std;

#define ll long long
#define pii pair<int, int>
#define oo 1e9

const int MAX = 1e5 + 5;

vector<pii> g[MAX];
int n, m;
bool visited[MAX];

pii dfs(int node, int p){
    visited[node] = 1;
    pii ans = {0, node};
    for(auto to : g[node]){
        if(to.first == p) continue;
        pii nw = dfs(to.first, node);
        nw.first += to.second;
        if(ans.first < nw.first) ans = nw;
    }
    return ans;
}

int biggestDist[MAX];
int smallestDist = oo;

int finalAns = 0;

void dfs2(int node, int p, int h){
    if(biggestDist[node] == -1){
        biggestDist[node] = h;
    }
    else{
        smallestDist = min(smallestDist, max(biggestDist[node], h));
    }
    for(auto to : g[node]){
        if(to.first == p) continue;
        dfs2(to.first, node, h + to.second);
    }
}

vector<int> v;

void findDia(int node){
    int a = dfs(node, node).second;
    int b = dfs(a, a).second;
    dfs2(a, a, 0);
    finalAns = max(finalAns, biggestDist[b]);
    dfs2(b, b, 0);
    v.push_back(smallestDist);
    smallestDist = oo;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    memset(biggestDist, -1, sizeof(biggestDist));
    n = N;
    m = M;
    for(int i = 0; i < m; i++){
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }
    for(int i = 0; i < n; i++){
        if(!visited[i]){
            findDia(i);
        }
    }
    sort(v.begin(), v.end());
    if(v.size() == 1){
        return finalAns;
    }
    if(v.size() == 2){
        return max(finalAns, (v[v.size() - 1] + L + v[v.size() - 2]));
    }
    return  max(max( (v[v.size() - 1] + L + v[v.size() - 2]) ,
            (v[v.size() - 2] + 2 * L + v[v.size() - 3]) ), finalAns);
}

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