#ifndef DREAMING_H_INCLUDED
#define DREAMING_H_INCLUDED
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl
typedef long long ll;
typedef pair<int, int> point;
const int MAXN = 1e5 + 5;
vector <point> E[MAXN];
vector <int> component[MAXN];
int boja[MAXN], dist[MAXN], dep[MAXN], mx[MAXN];
point par[MAXN];
void color(int x, int Time){
boja[x] = Time;
component[Time].pb(x);
for(auto e : E[x]){
if(boja[e.first] != -1) continue;
color(e.first, Time);
}
}
point find_furthest(int cmp, int x){
for(auto it : component[cmp])
dist[it] = 0;
queue<int> Q;
Q.push(x);
point ret = point(0, 0);
while(!Q.empty()){
int nx = Q.front(); Q.pop();
for(auto e : E[nx]){
if(dist[e.first] || e.first == x)
continue;
par[e.first] = point(nx, e.second);
dep[e.first] = dep[nx] + 1;
dist[e.first] = dist[nx] + e.second;
ret = max(ret, point(dist[e.first], e.first));
Q.push(e.first);
}
}
return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
REP(i, M){
E[ A[i] ].pb( point( B[i], T[i] ) );
E[ B[i] ].pb( point( A[i], T[i] ) );
}
memset(boja, -1, sizeof(boja));
int Time = 0;
REP(i, N)
if(boja[i] == -1)
color(i, Time ++);
int ret = 0;
REP(i, Time){
int a = find_furthest(i, component[i][0]).second;
point najdalji = find_furthest(i, a);
int b = najdalji.second, d = najdalji.first;
if(dep[a] < dep[b])
swap(a, b);
ret = max(ret, d);
mx[i] = d;
int sum = 0;
while(dep[a] != dep[b]){
sum += par[a].second;
a = par[a].first;
mx[i] = min(mx[i], max(d - sum, sum));
}
while(a != b){
sum += par[a].second;
mx[i] = min(mx[i], max(d - sum, sum));
sum -= par[a].second;
sum += par[b].second;
mx[i] = min(mx[i], max(d - sum, sum));
sum -= par[b].second;
sum += par[a].second;
sum += par[b].second;
a = par[a].first;
b = par[b].first;
mx[i] = min(mx[i], max(d - sum, sum));
}
}
sort(mx, mx + Time, greater<int>());
if(Time == 1)
return ret;
else
return max(ret, mx[0] + mx[1] + L);
}
#endif // DREAMING_H_INCLUDED
Compilation message
/tmp/ccSlrwNG.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
