#include <bits/stdc++.h>
#include"dreaming.h"
#define X first
#define Y second
#define pii pair<int, int>
#define pb push_back
using namespace std;
const int MN = 1000000010;
const int INF = 1e9 + 10;
int n, m, l;
int min_max[MN], c[MN];
int nxt[MN], maxp[MN], h[MN], nxte[MN];
bool mark[MN], bio[MN];
vector<pii> g[MN];
vector<int> used;
set<int> s;
int Find(int x){
//cout << x << " +\n";
if(h[x] == x)
return x;
return h[x] = Find(h[x]);
}
void Union(int x, int y){
h[x] = Find(y);
}
void use(int x){
if(!mark[x]){
used.pb(x);
mark[x] = true;
}
}
int maxPath(int x){
use(x);
bio[x] = true;
maxp[x] = 0;
int mi = x;
for(pair<int, int> e : g[x]){
int y = e.X;
if(bio[y])
continue;
int val = e.Y;
int f = maxPath(y);
if(maxp[y] + val > maxp[x]){
maxp[x] = maxp[y] + val;
mi = f;
nxt[x] = y;
nxte[x] = val;
}
}
//cout << x << " " << maxp[x] << " " << mi << "\n";
return mi;
}
void clearUsed(){
for(int x : used){
nxt[x] = 0;
maxp[x] = 0;
mark[x] = false;
bio[x] = 0;
nxte[x] = 0;
}
used.clear();
}
pii findCenter(int x, bool printp){
clearUsed();
x = maxPath(x);
clearUsed();
int y = maxPath(x);
int s = maxp[x];
int zb = 0;
if(printp){
return {s, 0};
}
int mn = INF, mni = x;
while(x != y){
if(mn > max(zb, s - zb)){
mn = max(zb, s - zb);
mni = x;
}
//cout << x << " -> " << nxt[x] << " (" << nxte[x] << " " << zb << ")\n";
zb += nxte[x];
x = nxt[x];
}
if(mn == INF)
mn = 0;
return {mni, mn};
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
ios_base::sync_with_stdio(false);
for(int i = 0; i < MN; i++){
h[i] = i;
c[i] = i;
}
//cin >> n >> m >> l;
n = N;
m = M;
l = L;
for(int i = 0; i < n; i++)
s.insert(i);
for(int i = 0; i < m; i++){
int a, b, t;
//cin >> a >> b >> t;
a = A[i];
b = B[i];
t = T[i];
g[a].push_back({b, t});
g[b].push_back({a, t});
a = Find(a);
b = Find(b);
s.erase(a);
s.erase(b);
Union(a, b);
s.insert(Find(a));
}
auto it = s.begin();
while(it != s.end()){
pii res = findCenter(*it, 0);
c[*it] = res.X;
min_max[*it] = res.Y;
it++;
}
while(s.size() > 1){
auto it = s.begin();
int a = *it;
it++;
int b = *it;
int ca = c[a], av = min_max[a];
int cb = c[b], bv = min_max[b];
s.erase(a);
s.erase(b);
Union(a, b);
g[ca].pb({cb, l});
g[cb].pb({ca, l});
int nh = Find(a);
s.insert(nh);
if(max(av, bv + l) > max(bv, av + l)){
swap(ca, cb);
swap(av, bv);
}
c[nh] = ca;
min_max[nh] = max(av, bv + l);
}
pii ret = findCenter(*(s.begin()), 1);
return ret.X;
}
/*
int main(){
int n, m, l;
int a[MN], b[MN], t[MN];
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";
return 0;
}*/
Compilation message
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
