//#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
const int N=1e5+4;
vector<array<int,2>>adj[N];
int d[N][2],vis[N],sigmaxorhash[N],par[N];
vector<int>passed;
void dfs(int u,bool x){
passed.push_back(u);
vis[u]=1;
for(auto&[v,w]:adj[u]){
if(vis[v])
continue;
d[v][x]=d[u][x]+w;
dfs(v,x);
}
}
void findpath(int u){
vis[u]=1;
for(auto&[v,w]:adj[u]){
if(vis[v])
continue;
par[v]=u;
sigmaxorhash[u]^=sigmaxorhash[v];
findpath(v);
}
}
void unq(vector<int>&v){
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
}
int findmxlen(int node){
d[node][0]=0;
dfs(node,0);
unq(passed);
int mx=-1,kraj1,kraj2;
for(int u:passed){
if(d[u][0]>mx){
mx=d[u][0];
kraj1=u;
}
vis[u]=0;
}
passed.clear();
d[kraj1][0]=0;
dfs(kraj1,0);
unq(passed);
mx=-1;
for(int u:passed){
if(d[u][0]>mx){
mx=d[u][0];
kraj2=u;
}
vis[u]=0;
}
passed.clear();
d[kraj2][1]=0;
dfs(kraj2,1);
unq(passed);
for(int u:passed){
sigmaxorhash[u]=0;
vis[u]=0;
par[u]=0;
}
sigmaxorhash[kraj1]=1;
sigmaxorhash[kraj2]=1;
findpath(kraj1);
unq(passed);
set<int>path;
for(int u:passed){
if(sigmaxorhash[u]){
path.insert(u);
if(par[u])path.insert(par[u]);
}
vis[u]=1;
}
int mnmxlen=1e18;
for(int v:path)
mnmxlen=min(mnmxlen,max(d[v][0],d[v][1]));
path.clear();
passed.clear();
return mnmxlen;
}
int jednostablo(int node=1){
d[node][0]=0;
dfs(node,0);
int mx=-1,kraj1;
for(auto&u:passed){
if(d[u][0]>mx){
mx=d[u][0];
kraj1=u;
}
vis[u]=0;
}
passed.clear();
d[kraj1][0]=0;
dfs(kraj1,0);
mx=-1;
for(auto&u:passed){
if(d[u][0]>mx)
mx=d[u][0];
vis[u]=0;
}
return mx;
}
int32_t travelTime(int32_t N, int32_t M, int32_t L, int32_t A[], int32_t B[], int32_t T[]) {
int n=N,m=M,l=L;
for(int i=0,u,v,w;i<m;++i){
u=A[i];
v=B[i];
w=T[i];
++u,++v;
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
if(m==n-1)
return jednostablo();
vector<int>poludijametri;
for(int i=1;i<=n;++i){
if(vis[i])
continue;
poludijametri.push_back(findmxlen(i));
}
sort(poludijametri.rbegin(),poludijametri.rend());
int ans=poludijametri[0]+poludijametri[1]+l;
if(poludijametri.size()>2)
ans=max(ans,poludijametri[1]+poludijametri[2]+2*l);
return ans;
}
Compilation message
dreaming.cpp: In function 'int64_t jednostablo(int64_t)':
dreaming.cpp:107:8: warning: 'kraj1' may be used uninitialized in this function [-Wmaybe-uninitialized]
107 | dfs(kraj1,0);
| ~~~^~~~~~~~~
dreaming.cpp: In function 'int64_t findmxlen(int64_t)':
dreaming.cpp:75:24: warning: 'kraj2' may be used uninitialized in this function [-Wmaybe-uninitialized]
75 | sigmaxorhash[kraj2]=1;
| ~~~~~~~~~~~~~~~~~~~^~
dreaming.cpp:76:13: warning: 'kraj1' may be used uninitialized in this function [-Wmaybe-uninitialized]
76 | findpath(kraj1);
| ~~~~~~~~^~~~~~~
/usr/bin/ld: /tmp/ccBML4HG.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
