#include "dreaming.h"
// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
using namespace std;
#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228
template<typename T> void uin(T &a, T b) {
if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
if (b > a) a = b;
}
random_device rnd;
template<typename T> void shuffle(vector< T > &v) {
for (int i = 1; i < (int)v.size(); ++i) {
swap(v[rnd() % i], v[i]);
}
for (int i = (int)v.size() - 1; i; --i) {
swap(v[rnd() % i], v[i]);
}
}
const int N = 100 * 1000 + 228;
const int INF = 1e9 + 1000000;
int n, m, L;
int down[N], up[N], f[N];
bool used[N];
vector< pair<int, int> > g[N];
vector<int> order;
void dfs1(int v, int par = -1) {
used[v] = 1;
down[v] = 0;
order.push_back(v);
for (pair<int, int> go : g[v]) {
int to = go.first, w = go.second;
if (to == par) continue;
dfs1(to, v);
uax(down[v], down[to] + w);
}
}
void dfs2(int v, int par = -1) {
vector< pair<int, int> > sons;
vector<int> value, pref, suff;
for (pair<int, int> go : g[v]) {
int to = go.first, w = go.second;
if (to == par) continue;
sons.emplace_back(to, w);
value.push_back(w + down[to]);
}
int sz = (int)sons.size();
pref.resize(sz + 2);
suff.resize(sz + 2);
for (int i = 0; i < sz; ++i) {
pref[i + 1] = max(value[i], pref[i]);
}
for (int i = sz; i; --i) {
suff[i] = max(suff[i + 1], pref[i - 1]);
}
for (int i = 1; i <= sz; ++i) {
int to = sons[i - 1].first, w = sons[i - 1].second;
uax(up[to], up[v] + w);
uax(up[to], w + max(pref[i - 1], suff[i + 1]));
}
for (int i = 0; i < sz; ++i) {
dfs2(sons[i].first, v);
}
}
vector<int> comp;
void pre() {
for (int i = 0; i < n; ++i) {
vector<int> dist(n, INF);
dist[i] = 0;
vector<int> q;
q.push_back(i);
for (int it = 0; it < (int)q.size(); ++it) {
int v = q[it];
for (pair<int, int> go : g[v]) {
if (dist[v] + go.second < dist[go.first]) {
dist[go.first] = dist[v] + go.second;
q.push_back(go.first);
}
}
}
for (int j = 0; j < n; ++j) {
if (dist[j] != INF) {
uax(f[i], dist[j]);
}
}
}
for (int i = 0; i < n; ++i) {
if (!used[i]) {
order.clear();
dfs1(i);
int value = f[order[0]];
for (int v : order) {
uin(value, f[v]);
}
comp.push_back(value);
}
}
// for (int i = 0; i < n; ++i) {
// if (!used[i]) {
// order.clear();
// dfs1(i);
// dfs2(i);
// for (int v : order) {
// f[v] = max(down[v], up[v]);
// }
// int value = f[order[0]];
// for (int v : order) {
// uin(value, f[v]);
// }
// comp.push_back(value);
// }
// }
}
int travelTime(int NN, int MM, int LL, int A[], int B[], int T[])
{
n = NN;
m = MM;
L = LL;
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]);
}
pre();
if (m == n - 1) {
return comp[0];
}
int res = L + comp[0] + comp[1];
for (int i = 0; i < n; ++i) {
uax(res, f[i]);
}
return res;
}
// int A[100], B[100], T[100];
// signed main() {
// cin >> n >> m >> L;
// for (int i = 0; i < m; ++i) {
// cin >> A[i] >> B[i] >> T[i];
// }
// cout << travelTime(n, m, L, A, B, T) << '\n';
// }
/*
12 8 2
0 8 2 5 5 1 1 10
8 2 7 11 1 3 9 6
4 2 4 3 7 1 5 3
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 |
| 1 |
Execution timed out |
1093 ms |
8012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
8012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
8012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1098 ms |
5496 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
8012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1093 ms |
8012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
