This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |