oj.uz

답안 #1004972

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1004972 2024-06-22T05:23:08 Z The_Samurai 꿈 (IOI13_dreaming) C++17
0 / 100
 32 ms 11484 KB 
#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;
    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]);
        // 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();
    }
    return mx1 + mx2 + L;
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 11484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 11484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 5720 KB Output is correct
2 Incorrect 12 ms 5724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 11484 KB Output isn't correct
2 Halted 0 ms 0 KB -