Submission #1004977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004977		The_Samurai	Dreaming (IOI13_dreaming)	C++17	100 / 100	46 ms	16040 KiB

dreaming

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

int travelTime(int n, int m, int L, int A[], int B[], int T[]) {
    vector<vector<pair<int, int>>> g(n);
    vector<bool> vis(n), vis2(n);
    for (int i = 0; i < m; i++) {
        g[A[i]].emplace_back(B[i], T[i]);
        g[B[i]].emplace_back(A[i], T[i]);
    }
    vector<int> h(n), dist(n), all;
    auto dfs = [&](auto &dfs, int u) -> void {
        all.emplace_back(u);
        vis[u] = true;
        for (auto [v, w]: g[u]) {
            if (vis[v]) continue;
            dfs(dfs, v);
            h[u] = max(h[u], h[v] + w);
        }
    };
    auto dfs2 = [&](auto &dfs2, int u, int came) -> void {
        // cout << '\t' << u << ' ' << came << endl;
        vis2[u] = true;
        int mx1 = 0, mx2 = 0;
        for (auto [v, w]: g[u]) {
            if (vis2[v]) continue;
            if (mx1 < h[v] + w) {
                mx2 = mx1;
                mx1 = h[v] + w;
            } else {
                mx2 = max(mx2, h[v] + w);
            }
        }
        dist[u] = max(came, h[u]);
        for (auto [v, w]: g[u]) {
            if (vis2[v]) continue;
            if (mx1 == h[v] + w) {
                dfs2(dfs2, v, max(came, mx2) + w);
            } else {
                dfs2(dfs2, v, max(came, mx1) + w);
            }
        }
    };
    multiset<int, greater<>> st;
    vector<int> shit;
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        dfs(dfs, i);
        dfs2(dfs2, i, 0);
        int mn = 1e9;
        for (int u: all) mn = min(mn, dist[u]);
        shit.emplace_back(mn);
        st.insert(mn);
        all.clear();
    }
    int ans = 2e9, dist_max = *max_element(dist.begin(), dist.end());
    if (st.size() == 1) return dist_max;
    if (st.size() == 2) {
        return max(dist_max, *st.begin() + *st.rbegin() + L);
    }
    for (int x: shit) {
        int now = dist_max;
        st.erase(st.find(x));
        now = max(now, x + L + *st.begin());
        auto it = st.begin();
        auto it2 = st.begin();
        it2++;

        now = max(now, *it + L + L + *it2);
        st.insert(x);
        ans = min(ans, now);
    }
    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