#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
#include "dreaming.h"
#endif
using namespace std;
using pii=pair<int,int>;
using vi=vector<int>;
#define ff first
#define ss second
const int MAXN = 100001;
vector<pair<int,int>> adj[MAXN];
bool vis[MAXN];
int dis[MAXN];
pair<int,int> antipode={-1,-1};
bool vis2[MAXN];
int dis2[MAXN];
pair<int,int> antipode2={-1,-1};
bool vis3[MAXN];
int semi_diam = -1;
bool found_end=false;
void dfs1(int v)
{
vis[v]=1;
for(auto u_raw:adj[v])
{
int u=u_raw.ff;
int d=u_raw.ss;
if(vis[u]) continue;
dis[u]=dis[v]+d;
antipode=max(antipode,{dis[u],u});
dfs1(u);
}
}
void dfs2(int v)
{
vis2[v]=1;
for(auto u_raw:adj[v])
{
int u=u_raw.ff;
int d=u_raw.ss;
if(vis2[u]) continue;
dis2[u]=dis2[v]+d;
antipode2=max(antipode2,{dis2[u],u});
dfs2(u);
}
}
void dfs3(int v)
{
vis3[v]=1;
if(v==antipode2.ss)
{
found_end=1;
}
for(auto u_raw:adj[v])
{
if(found_end) break;
int u=u_raw.ff;
if(vis3[u]) continue;
dfs3(u);
}
if(found_end)
{
semi_diam=min(semi_diam,max(antipode2.ff-dis2[u],dis2[u]));
}
}
int travelTime(int n, int m, int l, int A[], int B[], int T[])
{
vector<pair<int,int>> di_sdi; // aint the diameter, semi-diameter pairs
for(int i=0; i<m; i++)
{
adj[A[i]].push_back(make_pair(B[i],int(T[i])));
adj[B[i]].push_back(make_pair(A[i],int(T[i])));
}
for(int i=0; i<n; i++)
{
if(vis[i]) continue;
dfs1(i);
if(antipode == make_pair(int(-1),-1))
{
di_sdi.push_back({0,0});
continue;
}
dfs2(antipode.ss);
found_end=0;
semi_diam=int(1e9);
dfs3(antipode.ss); // don't think that this need be from antipode2.ss
di_sdi.push_back({semi_diam,antipode2.ff});
antipode={-1,-1};
antipode2={-1,-1};
}
// for(auto SD:di_sdi)
// {
// cout << SD.ff << " " << SD.ss << endl;
// }
sort(di_sdi.rbegin(),di_sdi.rend());
int ans=0;
for(auto SD:di_sdi) ans=max(ans,SD.ss);
if(di_sdi.size()>=3) ans=max(ans,int(l + l) + di_sdi[1].ff + di_sdi[2].ff);
if(di_sdi.size()>=2) ans=max(ans,int(l) + di_sdi[0].ff + di_sdi[1].ff);
// cout << ans << endl;
return ans;
}
Compilation message
dreaming.cpp: In function 'void dfs3(int)':
dreaming.cpp:84:49: error: 'u' was not declared in this scope
semi_diam=min(semi_diam,max(antipode2.ff-dis2[u],dis2[u]));
^
