// #include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
#define pr pair
typedef pr<ll, ll> prll;
#define f0r(i,a,n) for (i=a; i<n; i++)
#define f1r(i,a,n) for (i=a; i<=n; i++)
#define r0f(i,n,a) for (i=n; i>a; i--)
#define r1f(i,n,a) for (i=n; i>=a; i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define in(s, x) ((s).find((x)) != (s).end())
#define all(x) (x).begin(), (x).end()
#define allrev(x) (x).rbegin(), (x).rend()
inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }
#define INF (LLONG_MAX>>4ll)
#define mxN 100'010ll
ll n, m, l;
int *uar, *var, *war;
vc<vc<prll>> gr(mxN); // fi is w, se is v
vcll ar;
inline void build_gr()
{
ll i;
f0r(i,0,m)
{
ll u, v, w;
u=uar[i];
v=var[i];
w=war[i];
gr[u].pb({w, v});
gr[v].pb({w, u});
}
}
vc<bool> seen(mxN, 0);
map<prll, ll> from_to; // the "to" gives the value
inline void init_umap()
{
ll u;
f0r(u,0,n)
{
from_to[mp(-1,u)]=-1;
for (prll edge : gr[u])
{
ll v = edge.se;
from_to[mp(u,v)]=-1;
from_to[mp(v,u)]=-1;
}
}
}
vcll comp; // comp for component
void dfs(ll u)
{
if (seen[u]) return;
// printf("real, u: %lli\n", u);
seen[u]=1;
comp.pb(u);
for (prll edge : gr[u])
{
ll v=edge.se;
dfs(v);
}
}
ll calc_from_to(ll p, ll u)
{
ll &t = from_to[mp(p,u)];
// if (t!=-1) printf("p: %lli, u: %lli, t: %lli\n", p, u, t);
if (t!=-1) return t;
ll m=0; // max
for (prll edge : gr[u])
{
ll v=edge.se;
if (v==p) continue;
ll w=edge.fi;
maxa(m, calc_from_to(u,v)+w);
}
// printf("res: %lli\n", m);
return t=m;
}
inline ll minmaxdist(ll u)
{
comp.clear();
dfs(u);
// printf("comp.size: %lli\n", (ll)comp.size());
ll m=INF; // min
for (ll u : comp)
{
mina(m, calc_from_to(-1, u));
// printf("min: %lli\n", m);
}
// printf("true\n");
return m;
}
inline void build_ar()
{
init_umap();
ll u;
f0r(u,0,n)
{
if (seen[u]) continue;
ar.pb(minmaxdist(u));
// printf("ar.back(): %lli\n", ar.back());
}
}
inline ll value()
{
ll z=ar.size();
// printf("z: %lli\n", z);
if (z==1) return ar[0];
if (z==2) return ar[0]+ar[1]+l;
return max(ar[0]+ar[1]+l, ar[1]+ar[2]+(2*l));
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
n=N;
m=M;
l=L;
uar=A;
var=B;
war=T;
build_gr();
build_ar();
sort(allrev(ar));
return value();
}
/*
int main()
{
freopen("dreaming.in", "r", stdin);
int N, M, L, *A, *B, *T;
A=new int[mxN];
B=new int[mxN];
T=new int[mxN];
cin >> N >> M >> L;
ll i;
f0r(i,0,M) cin >> A[i] >> B[i] >> T[i];
int v = travelTime(N, M, L, A, B, T);
printf("ans: %i\n", v);
return 0;
}
*/
Compilation message
/usr/bin/ld: /tmp/ccE6jvvE.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
