#include <bits/stdc++.h>
#include "dreaming.h"
#define pb push_back
//#define int long long
#define F first
#define S second
using namespace std;
const int N = 1e5+10;
const int mod = 1e9+7;
const int inf = 1e18;
vector<pair<int,int>>g[N];
vector<int>all,dist(N),vis(N);
void dfs(int x,int par) {
all.pb(x);
for(auto X:g[x]) {
if(X.F != par) {
dist[X.F] = dist[x] + X.S;
dfs(X.F,x);
}
}
}
pair<int,int>nadji_precnik(int root) {
int x,y;
all.clear();
dist[root] = 0;
dfs(root,0);
int mx = 0,idx = -1;
for(auto X:all) {
if(dist[X] >= mx) {
mx = dist[X];
idx = X;
}
}
x = idx;
mx = 0,idx = -1;
all.clear();
dist[x] = 0;
dfs(x,0);
for(auto X:all) {
//cout << "X = " << X << " dist[x] = " << dist[X] << endl;
if(dist[X] >= mx) {
mx = dist[X];
idx = X;
}
}
//cout << endl;
//cout << idx << endl;
y = idx;
//if(root == 4) cout << "x = " << x << " y = " << y << endl;
return {x,y};
}
void obelezi(int x) {
if(vis[x]) return;
vis[x] = 1;
for(auto X:g[x]) obelezi(X.F);
}
int travelTime(int N,int M,int L,vector<int>A,vector<int>B,vector<int>T) {
for(int i=0;i<M;i++) {
g[A[i]].pb({B[i],T[i]});
g[B[i]].pb({A[i],T[i]});
}
vector<int>centers;
for(int i=0;i<N;i++) {
if(vis[i]) continue;
//cout << i << endl;
all.clear();
dfs(i,0);
vector<int>all_in_comp = all;
pair<int,int>dia = nadji_precnik(i);
int X = dia.F,Y = dia.S;
//if(i == 4) cout << X << ' ' << Y << endl;
dist[X] = 0;
dfs(X,0);
map<int,int>D;
for(auto XX:all_in_comp) D[XX] = dist[XX];
dist[Y] = 0;
dfs(Y,0);
for(auto XX:all_in_comp) D[XX] = max(D[XX],dist[XX]);
int mn = 1e9,idx = -1;
for(auto XX:all_in_comp) {
if(D[XX] < mn) {
mn = D[XX];
idx = XX;
}
}
//cout << "root = " << i << " dia = " << X << " " << Y << endl;
//cout << "root = " << i << " center = " << idx << endl;
centers.pb(idx);
obelezi(i);
}
for(int i=1;i<centers.size();i++) {
g[centers[i-1]].pb({centers[i],L});
g[centers[i]].pb({centers[i-1],L});
}
pair<int,int> res = nadji_precnik(1);
dist[res.F] = 0;
dfs(res.F,0);
int index = 0;
for(int i=0;i<N;i++) {
if(dist[index] <= dist[i]) index = i;
}
return dist[index];
}
/*signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m,l;
cin >> n >> m >> l;
vector<int>a(m),b(m),c(m);
for(int i=0;i<m;i++) cin >> a[i];
for(int i=0;i<m;i++) cin >> b[i];
for(int i=0;i<m;i++) cin >> c[i];
cout << travelTime(n,m,l,a,b,c);
return 0;
}*/
Compilation message
dreaming.cpp:19:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
19 | const int inf = 1e18;
| ^~~~
dreaming.cpp: In function 'int travelTime(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
dreaming.cpp:105:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i=1;i<centers.size();i++) {
| ~^~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccc5IbwI.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
