#include<bits/stdc++.h>
#include"dreaming.h"
using namespace std;
typedef long long ll;
const int maxn = 1e5;
vector<vector<pair<int, int>>> g(maxn+5);
vector<bool> vis(maxn+5, false);
vector<int> dt(maxn+5), ht(maxn+5, 0), group(maxn+5);
vector<multiset<int>> S(maxn+5);
void dfs1(int v, int P){
group[v] = P;
vis[v] = 1;
int maxi1 = 0, maxi2 = 0;
for(pair<int, int> pp : g[v]){
int u = pp.first, w = pp.second;
if(vis[u])
continue;
dfs1(u, P);
ht[v] = max(ht[v], ht[u]+w);
if(ht[u]+w >= maxi1){
maxi2 = maxi1, maxi1 = ht[u]+w;
} else if(ht[u]+w >= maxi2){
maxi2 = ht[u]+w;
}
}
dt[v] = maxi1+maxi2;
}
void dfs2(int v, int p){
vis[v] = 1;
for(pair<int, int> pp : g[v]){
int u = pp.first, w = pp.second;
if(u == p)
continue;
S[v].insert(ht[u]+w);
}
for(pair<int, int> pp : g[v]){
int u = pp.first, w = pp.second;
if(u == p)
continue;
if(S[v].size() == 1){
S[u].insert(w);
} else if(!S[v].empty()){
S[v].erase(S[v].find(ht[u]+w));
int best = *--S[v].end();
S[u].insert(best+w);
S[v].insert(ht[u]+w);
}
}
if(!S[v].empty())
ht[v] = *--S[v].end();
for(pair<int, int> pp : g[v]){
int u = pp.first, w = pp.second;
if(vis[u])
continue;
dfs2(u, 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++){
g[A[i]].emplace_back(B[i], T[i]);
g[B[i]].emplace_back(A[i], T[i]);
}
for(int i = 0; i < N; i++)
if(!vis[i])
dfs1(i, i);
fill(vis.begin(), vis.end(), false);
for(int i = 0; i < N; i++)
if(!vis[i])
dfs2(i, -1);
int ans = 0;
for(int i = 0; i < N; i++)
ans = max(ans, dt[i]);
vector<pair<int, int>> order;
order.reserve(N);
for(int i = 0; i < N; i++)
order.emplace_back(ht[i], group[i]);
sort(order.begin(), order.end());
vector<int> G;
G.reserve(N);
vector<bool> used(N+5, false);
for(int i = 0; i < N; i++){
if(used[order[i].second])
continue;
G.emplace_back(order[i].first);
used[order[i].second] = true;
}
int GN = G.size();
sort(G.begin(), G.end(), [&](int n1, int n2){
return n1 > n2;
});
for(int i = GN-1; i > 0; i--)
ans = max(ans, G[0] + G[i] + i*L);
return ans;
}
Compilation message
dreaming.cpp: In function 'void dfs2(int, int)':
dreaming.cpp:56:23: warning: unused variable 'w' [-Wunused-variable]
56 | int u = pp.first, w = pp.second;
| ^
/usr/bin/ld: /tmp/ccecIAf3.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
