// code by: Karlo Brcic
// Dreaming, IOI 2013
#include <bits/stdc++.h>
using namespace std;
//int A [100010], B [100010], T [100010];
vector < pair <int, int> > g [100010];
int bio [100010];
vector <int> rad; vector < pair <int, int> > red;
int maxi=-1, maxi2;
int dfs (int x, int par, int zapis, int tre){ // returns the furtherest point from x
int ans=0; bio [x]=1; int tko=-1; int dulj=-1;
if (tre>maxi){
maxi=tre; maxi2=x;
}
for (int i=0; i<g[x].size(); i++){
int y=g[x][i].first;
if (y==par) continue;
if (ans<dfs (y, x, zapis, tre+g[x][i].second)+g[x][i].second){
ans=dfs (y, x, zapis, tre+g[x][i].second)+g[x][i].second;
tko=y; dulj=g[x][i].second;
}
}
if (tko!=-1 && zapis){
red.push_back ({tko, dulj});
}
//cout << x << " " << ans << endl;
return ans;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]){
for (int i=0; i<M; i++){
int a=A [i];
int b=B [i];
int c=T [i];
g [a].push_back ({b, c});
g [b].push_back ({a, c});
}
int ans=-1;
for (int i=0; i<N; i++){
if (bio [i]) continue;
red.clear();
maxi=-1;
int fur1=dfs (i, -1, 0, 0);
maxi=-1;
int fur2=dfs (maxi2, -1, 1, 0);
ans=max (ans, fur2);
reverse (red.begin(), red.end());
int tre=0; int r=fur2;
for (int j=0; j<red.size(); j++){
tre+=red[j].second;
r=min (r, max (tre, fur2-tre));
}
rad.push_back (r);
//cout << fur2 << endl;
}
sort (rad.rbegin(), rad.rend());
if (rad.size()>=2){
ans=max (ans, rad [0]+rad[1]+L);
}
if (rad.size()>=3){
ans=max (ans, rad [1]+rad[2]+2*L);
}
return ans;
}
/*int main (){
int n, m, l; 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);
return 0;
}*/
Compilation message
dreaming.cpp: In function 'int dfs(int, int, int, int)':
dreaming.cpp:15:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | for (int i=0; i<g[x].size(); i++){
| ~^~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int j=0; j<red.size(); j++){
| ~^~~~~~~~~~~
dreaming.cpp:42:7: warning: unused variable 'fur1' [-Wunused-variable]
42 | int fur1=dfs (i, -1, 0, 0);
| ^~~~
/usr/bin/ld: /tmp/ccbAujTx.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
