#include "grader.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], value[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) {
down[i] = up[i] = 0;
}
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]);
}
// if (n <= 100) exit(-1);
pre();
if (m == n - 1) {
int res = 0;
for (int i = 0; i < n; ++i) {
uax(res, f[i]);
}
return res;
}
if (m == n - 2) {
int res = L + comp[0] + comp[1];
for (int i = 0; i < n; ++i) {
uax(res, f[i]);
}
return res;
}
sort(comp.rbegin(), comp.rend());
int res = 0;
uax(res, comp[0] + comp[1] + L);
uax(res, comp[1] + comp[2] + 2 * L);
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
*/
Compilation message
dreaming.cpp:1:10: fatal error: grader.h: No such file or directory
#include "grader.h"
^~~~~~~~~~
compilation terminated.
