This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using pii = pair<int, int>;
using ll = int64_t;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n';
constexpr int mxN = 1e5 + 20;
vector<pii> g[mxN];
int par[mxN], dist[mxN], current_root = 0;
bool vis[mxN];
void dfs(int x, int p, int& tr) {
if (dist[x] > dist[tr]) {
tr = x;
}
if (p == -1) {
dist[x] = 0;
}
par[x] = p;
vis[x] = true;
for (auto ptr: g[x]) {
if (ptr.first != p) {
dist[ptr.first] = dist[x] + ptr.second;
dfs(ptr.first, x, tr);
}
}
}
int travelTime(int N, int M, int L, int* A, int* B, int* T) {
for (int i = 0; i < M; i++) {
g[A[i]].push_back({B[i], T[i]});
g[B[i]].push_back({A[i], T[i]});
}
for (int i = 0; i < N; i++) {
vis[i] = false;
dist[i] = 0;
}
vector<int> vv;
int ans = 0;
for (int i = 0; i < N; i++) {
if (!vis[i]) {
int root = i;
current_root = i;
dfs(i, -1, root);
int diamend = i;
dfs(root, -1, diamend);
int distance = dist[diamend];
ans = max(ans, distance);
for (int ptr = diamend; ptr != -1; ptr = par[ptr]) {
dbg(ptr);
distance = min(distance, max(dist[ptr], dist[diamend] - dist[ptr]));
}
vv.push_back(distance);
dbg(distance);
}
}
sort(rall(vv));
if (vv.size() == 1) {
return max(ans, vv[0]);
} else if (vv.size() == 2) {
return max(ans, vv[0] + vv[1] + L);
}
ans = max(ans, vv[0] + vv[1] + L);
ans = max(ans, vv[1] + vv[2] + 2 * L);
return ans;
}
/*int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cout.tie(nullptr); cerr.tie(nullptr);
int n, m, l;
cin >> n >> m >> l;
int a[m], b[m], t[m];
for (int i = 0; i < m; i++) {
cin >> a[i] >> b[i] >> t[i];
}
int ans = travelTime(n, m, l, a, b, t);
cout << ans << '\n';
return 0;
}*/
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
# | 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... |