#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ii pair<int, int>
#define f1 first
#define s2 second
int const inf = 1e9 + 7;
vector<vector<ii>> adj;
vector<ii> dst; //furthest and second furthest distance from vertex
vector<bool> vst;
vector<int> vertices;
inline ii combine(ii x, int y)
{
int a = max(max(x.f1, x.s2), y);
int b = x.f1 + x.s2 + y - a - min(min(x.f1, x.s2), y);
return {a, b};
}
void dfs(int node)
{
vst[node] = true;
vertices.pb(node);
for (ii to : adj[node])
{
if (!vst[to.f1])
{
dfs(to.f1);
dst[node] = combine(dst[node], to.s2 + dst[to.f1].f1);
}
}
}
void reroot(int node)
{
vst[node] = true;
for (ii to : adj[node])
{
if (!vst[to.f1])
{
if (dst[node].f1 == to.s2 + dst[to.f1].f1)
dst[to.f1] = combine(dst[to.f1], to.s2 + dst[node].s2);
else dst[to.f1] = combine(dst[to.f1], to.s2 + dst[node].f1);
reroot(to.f1);
}
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
adj.resize(N);
dst.assign(N, {0, 0});
vst.assign(N, false);
for (int i = 0; i < M; ++i)
adj[A[i]].pb({B[i], T[i]}), adj[B[i]].pb({A[i], T[i]});
vector<int> candidate; //vertice connecting with other tree
for (int i = 0; i < N; ++i)
{
if (!vst[i])
{
vertices.clear();
dfs(i);
for (int x : vertices)
vst[x] = false;
reroot(i);
int best = vertices[0];
for (int x : vertices)
{
if (dst[best].f1 > dst[x].f1)
best = x;
}
candidate.pb(best);
}
}
int best = candidate[0];
for (int x : candidate)
{
//cerr << x << ": " << dst[x].f1 << '\n';
if (dst[best].f1 < dst[x].f1)
best = x;
}
for (int x : candidate)
{
if (best != x)
adj[best].pb({x, L}), adj[x].pb({best, L});
}
dst.assign(N, {0, 0});
vst.assign(N, false);
dfs(0);
vst.assign(N, false);
reroot(0);
int res = 0;
for (int i = 0; i < N; ++i)
res = max(res, dst[i].f1);
return res;
}
Compilation message
stations.cpp:1:10: fatal error: dreaming.h: No such file or directory
1 | #include "dreaming.h"
| ^~~~~~~~~~~~
compilation terminated.
