#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = (l), _r = (r); i < _r; ++i)
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define ROF(i, r, l) for(int i = (r), _l = (l); i >= _l; --i)
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
template<typename T>
bool minimize(T& a, const T& b){
if(a > b) return a = b, true; return false;
}
template<typename T>
bool maximize(T& a, const T& b){
if(a < b) return a = b, true; return false;
}
using ll = long long;
using ld = long double;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> T random_int(T l, T r){ return uniform_int_distribution<T>(l, r)(rng); }
template<typename T> T random_real(T l, T r){ return uniform_real_distribution<T>(l, r)(rng); }
const int MAX = 1e5 + 5;
bool vis[MAX];
int dp_children[MAX], dp_not_children[MAX], dp_diameter[MAX], minBest[MAX];
vector<pair<int, int>> adj[MAX];
void dfs1(int u, int p = -1){
vis[u] = true;
for(auto [v, w] : adj[u]) if(v != p){
adj[v].erase(find(all(adj[v]), make_pair(u, w)));
dfs1(v);
maximize(dp_diameter[u], dp_children[v] + w + dp_children[u]);
maximize(dp_children[u], dp_children[v] + w);
maximize(dp_diameter[u], dp_diameter[v]);
}
}
void dfs2(int u, int p = -1){
minBest[u] = max(dp_children[u], dp_not_children[u]);
vector<int> pref, suff;
for(auto [v, w] : adj[u]) if(v != p){
pref.push_back(dp_children[v] + w);
}
suff = pref;
for(int i = 1; i < sz(pref); ++i){
pref[i] = max(pref[i - 1], pref[i]);
}
for(int i = sz(pref) - 2; i >= 0; --i){
suff[i] = max(suff[i], suff[i + 1]);
}
int i = 0;
for(auto [v, w] : adj[u]) if(v != p){
int l = (i > 0 ? pref[i - 1] : 0);
int r = (i + 1 < sz(suff) ? suff[i + 1] : 0);
dp_not_children[v] = w + max({dp_not_children[u], l, r});
++i;
dfs2(v);
minimize(minBest[u], minBest[v]);
}
}
int travelTime(int N, int M, int L, vector<int> A, vector<int> B, vector<int> T){
for(int i = 0; i < M; ++i){
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
int ans = 0;
vector<int> r, diamter;
for(int i = 0; i < N; ++i){
if(!vis[i]){
r.push_back(i);
dfs1(i);
ans = max(ans, dp_diameter[i]);
}
}
vector<int> solutions;
fill(vis, vis + N, false);
for(int rt : r){
dfs2(rt);
solutions.push_back(minBest[rt]);
}
if(sz(solutions) == 1){
return ans;
}
sort(all(solutions), greater<int>());
int merge_solutions = 0;
if(sz(solutions) == 2){
merge_solutions = L + solutions[0] + solutions[1];
} else{
merge_solutions = max(L + solutions[0] + solutions[1], L + solutions[1] + L + solutions[2]);
}
return max(merge_solutions, ans);
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << travelTime(12, 8, 2, {0, 8, 2, 5, 5, 1, 1, 10}, {8, 2, 7, 11, 1, 3, 9, 6}, {4, 2, 4, 3, 7, 1, 5, 3}) << '\n';
return 0;
}
#endif
Compilation message
dreaming.cpp: In function 'bool minimize(T&, const T&)':
dreaming.cpp:15:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
15 | if(a > b) return a = b, true; return false;
| ^~
dreaming.cpp:15:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
15 | if(a > b) return a = b, true; return false;
| ^~~~~~
dreaming.cpp: In function 'bool maximize(T&, const T&)':
dreaming.cpp:20:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
20 | if(a < b) return a = b, true; return false;
| ^~
dreaming.cpp:20:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
20 | if(a < b) return a = b, true; return false;
| ^~~~~~
dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:38:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
38 | for(auto [v, w] : adj[u]) if(v != p){
| ^
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:50:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
50 | for(auto [v, w] : adj[u]) if(v != p){
| ^
dreaming.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
65 | for(auto [v, w] : adj[u]) if(v != p){
| ^
/usr/bin/ld: /tmp/ccjhREbJ.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
