//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "grader.h"
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
vii adj[MAXN];
int vis[MAXN], arr[MAXN];
int sz[MAXN], dp2[MAXN];
pair<pii,pii> dp[MAXN];
int ans = 0;
int dfs(int u, int p, int d, int comp) {
arr[u] = comp;
vis[u] = 1;
int mx = 0, mx2 = 0;
int ind = -1;
for (pii nx: adj[u]) {
if (nx.fi == p)
continue;
int v = nx.fi;
int tmp = dfs(v, u, d + nx.se, comp) + nx.se;
if (mx < tmp) {
mx2 = mx;
mx = tmp;
dp[u] = {{mx, v}, {mx2, ind}};
ind = v;
} else if (mx2 < tmp) {
mx2 = tmp;
dp[u].se = {mx2, v};
}
}
ans = max(ans, mx + mx2);
return mx;
}
void dfs2(int u, int p, int w) {
if (p != -1) {
if (dp[p].fi.se == u)
dp2[u] = max(w + dp2[p], w + dp[p].se.fi);
else
dp2[u] = max(w + dp2[p], w + dp[p].fi.fi);
}
for (pii v: adj[u])
if (v.fi != p)
dfs2(v.fi, u, v.se);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
/*int n, m, l;
scanf("%d %d %d", &n, &m, &l);*/
for (int i = 0; i < m; i++) {
/*int a, b, t;
scanf("%d %d %d", &a, &b, &t);*/
adj[a[i]].pb({b[i], t[i]});
adj[b[i]].pb({a[i], t[i]});
}
int comp = 0;
for (int i = 0; i < n; i++) {
if (vis[i])
continue;
dfs(i, -1, 0, comp);
dfs2(i, -1, 0);
sz[comp] = INF;
comp++;
}
for (int i = 0; i < n; i++)
sz[arr[i]] = min(sz[arr[i]], max(dp2[i], dp[i].fi.fi));
sort(sz, sz + comp);
if (comp > 1)
ans = max(ans, sz[comp - 1] + l + sz[comp - 2]);
if (comp > 2)
ans = max(ans, sz[comp - 2] + 2 * l + sz[comp - 3]);
//pri(ans);
return ans;
}
/*int main()
{
return 0;
}*/
Compilation message
dreaming.cpp:3:10: fatal error: grader.h: No such file or directory
#include "grader.h"
^~~~~~~~~~
compilation terminated.
