#include <bits/stdc++.h>
#include "dreaming.h"
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define int long long
const int N = 1e5+1;
vector <pair<int,int>> g[N];
int used[N], Mx, it, diameter;
array <int,2> dis[N];
vector <int> V;
void dfs(int x, int par, int depth, int itr){
if ( itr == -1 ) V.pb(x);
else dis[x][itr] = depth;
if ( depth > Mx ){
Mx = depth, it = x;
}
for ( auto [to, len]: g[x] ){
if ( to == par ) continue;
dfs(to, x, depth+len, it);
}
}
int best(int root){
dfs(root, root, 0, -1); Mx = 0;
dfs(it, it, 0, 0); Mx = 0;
dfs(it, it, 0, 1);
diameter = max(diameter, Mx);
Mx = 0;
int Mn = 1e9;
for ( auto i: V ){
used[i] = true;
Mn = min(Mn, max(dis[i][0], dis[i][1]));
}
V.clear();
return Mn;
}
int travelTime(int n, int M, int L, int A[], int B[], 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> res;
for ( int i = 0; i < n; i++ ){
if ( used[i] ) continue;
res.pb(best(i));
}
sort(all(res), greater <int> ());
int Mx = diameter;
if ( (int)res.size() > 1 ) Mx = max(Mx, res[0]+res[1]+L);
if ( (int)res.size() > 2 ){
Mx = max(Mx, res[1]+res[2]+L*2);
}
return Mx;
}
#if false
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, M, L; cin >> n >> M >> L;
int A[M], B[M], T[M];
for ( int i = 0; i < M; i++ ){
cin >> A[i] >> B[i] >> T[i];
}
cout << travelTime(n, M, L, A, B, T);
cout << '\n';
/*
12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/
}
#endif
Compilation message
dreaming.cpp: In function 'void IO(std::string)':
dreaming.cpp:12:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:12:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
42 ms |
21796 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
42 ms |
21796 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
6616 KB |
Output is correct |
2 |
Correct |
23 ms |
7160 KB |
Output is correct |
3 |
Incorrect |
25 ms |
7116 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
42 ms |
21796 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |