제출 #1289484

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289484		zaresrdic26	꿈 (IOI13_dreaming)	C++20	100 / 100	162 ms	18720 KiB

dreaming

#include <iostream>
#include <cstdio>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <limits>
#include <tuple>
#include <stack>
#include <bitset>
#include <cstring>
#include <sstream>
#include <functional>
#include <random>
#include "dreaming.h"
using namespace std;

using ll = long long;
const ll inf = (1ll << 60);

vector<vector<pair<int, int>>> adj;
vector<int> par;
vector<bool> vis;
vector<int> comp;
vector<bool> incomp;
vector<ll> distg;

int compB = -1, compC = -1;

void mark_cmp(int u) {
    vis[u] = true;
    comp.push_back(u);
    for (auto& e : adj[u]) {
        int v = e.first;
        if (!vis[v]) {
            mark_cmp(v);
        }
    }
}

void dfs(int u, int p, ll d, pair<int, ll>& mx) {
    distg[u] = d;
    if (d > mx.second) {
        mx = { u, d };
    }
    par[u] = p;
    for (auto& e : adj[u]) {
        int v = e.first, w = e.second;
        if (v == p) {
            continue;
        }
        dfs(v, u, d + w, mx);
    }
}

pair<int, ll> find_centar(int s) {
    for (auto& v : comp) {
        par[v] = -1;
        distg[v] = 0;
    }
    pair<int, ll> mx = { -1, -1 };
    dfs(s, -1, 0, mx);
    int B = mx.first;

    for (auto& v : comp) {
        par[v] = -1;
        distg[v] = 0;
    }
    mx = { -1, -1 };
    dfs(B, -1, 0, mx);
    int C = mx.first;
    ll tot = mx.second;
    compB = B, compC = C;

    vector<int> path;
    for (int v = C; v != -1; v = par[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());

    vector<int> dist(path.size(), 0);
    for (int i = 1; i < path.size(); ++i) {
        int a = path[i - 1], b = path[i];
        for (auto& e : adj[a]) {
            if (e.first == b) {
                dist[i] = dist[i - 1] + e.second;
                break;
            }
        }
    }
    for (int i = 0; i < path.size(); ++i) {
        if (dist[i] * 2 >= tot) {
            return { path[i], tot };
        }
    }
    return { path.back(), tot };
}

int mx_dist(int s) {    
    for (auto& v : comp) {
        par[v] = -1;
        distg[v] = 0;
    }
    pair<int, ll> mx = { -1, -1 };
    dfs(s, -1, 0, mx);
    return mx.second;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int n, m, l;
    n = N, m = M, l = L;
    adj.assign(n, {});
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        u = A[i], v = B[i], w = T[i];
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    vis.assign(n, false);
    par.assign(n, -1);
    distg.assign(n, 0);

    vector<ll> distB(n, inf), distC(n, inf);
    vector<ll> c;
    c.reserve(n);
    ll pom = 0;
    for (int u = 0; u < n; ++u) {
        if (!vis[u]) {
            comp.clear();
            mark_cmp(u);
            for (auto& v : comp) {
                par[v] = -1;
                distg[v] = 0;
            }
            pair<int, ll> x = find_centar(u);
            for (auto& v : comp) {
                distB[v] = inf;
            }
            for (auto& v : comp) {
                par[v] = -1;
                distg[v] = 0;
            }

            pair<int, ll> mx = { -1, -1 };
            dfs(compB, -1, 0, mx);
            for (auto& v : comp) {
                distB[v] = distg[v];
            }

            for (auto& v : comp) {
                distC[v] = inf;
            }
            for (auto& v : comp) {
                par[v] = -1;
                distg[v] = 0;
            }

            mx = { -1, -1 };
            dfs(compC, -1, 0, mx);
            for (auto& v : comp) {
                distC[v] = distg[v];
            }

            ll r = inf;
            for (auto& v : comp) {
                ll ecc = max(distB[v], distC[v]);
                if (ecc < r) {
                    r = ecc;
                }
            }
            c.push_back(r);
            pom = max(pom, x.second);
        }
    }
    ll ans = pom;
    sort(c.rbegin(), c.rend());
    if (c.size() == 1) {
        //ans = pom;
    }
    else if (c.size() == 2) {
        ans = max(ans, c[0] + l + c[1]);
    }
    else {
        ans = max({ ans, c[1] + l + c[0], c[1] + 2ll * l + c[2] });
    }
    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