제출 #1004973

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1004973		The_Samurai	Dreaming (IOI13_dreaming)	C++17	47 / 100	49 ms	16068 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);
            }
        }
    };
    int mx1 = 0, mx2 = 0, cnt = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        cnt++;
        dfs(dfs, i);
        dfs2(dfs2, i, 0);
        int mn = 1e9;
        for (int u: all) mn = min(mn, dist[u]);
        for (int u: all) ans = max(ans, dist[u]);
        // for (int u: all) {
        //     cout << u << ' ' << dist[u] << endl;
        // }
        // cout << endl;
        if (mx1 < mn) {
            mx2 = mx1;
            mx1 = mn;
        } else {
            mx2 = max(mx2, mn);
        }
        all.clear();
    }
    if (cnt == 1) return ans;
    return max(mx1 + mx2 + L, ans);
}

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