#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
vector <pair<int,int> > temp;
vector <vector <pair <int,int> > > adj;
int TreeRadius[200003];
int TreeDiameter[200003];
int check[200003];
int check2[200003];
int DistFromRoot[200003];
int DistFromEndpoint[200003];
int Previ[200003];
pair <int,int> TreeStats[200003];
int travelTime(int N, int M, int L, vector<int> A, vector <int> B, vector <int> T){
int n,m,len,dist,s,e;
n=N;
m=M;
len=L;
for(int i=0;i<=n+1;i++){
adj.push_back(temp);
}
for(int i=1;i<=m;i++){
s=A[i-1];
e=B[i-1];
dist=T[i-1];
adj[s].push_back({e,dist});
adj[e].push_back({s,dist});
}
int cnt=1;
int CFurthest;
int CMid;
int FirstEndpoint;
int SecondEndpoint;
int cur;
vector <int> clist;
for(int i=0;i<n;i++){
CFurthest=0;
CMid=1999999999;
cur=0;
clist.clear();
if(check[i]==0){
clist.push_back(i);
check[i]=cnt;
DistFromRoot[i]=0;
TreeRadius[cnt]=0;
while(cur<clist.size()){
for(int k=0;k<adj[clist[cur]].size();k++){
if(!check[adj[clist[cur]][k].first]){
clist.push_back(adj[clist[cur]][k].first);
DistFromRoot[adj[clist[cur]][k].first]=DistFromRoot[clist[cur]]+adj[clist[cur]][k].second;
if(DistFromRoot[adj[clist[cur]][k].first] > CFurthest){
CFurthest=DistFromRoot[adj[clist[cur]][k].first];
FirstEndpoint=adj[clist[cur]][k].first;
}
check[adj[clist[cur]][k].first]=cnt;
}
}
cur++;
}
if(clist.size()>1){
//TreeRadius[cnt]=1999999999;
}
clist.push_back(FirstEndpoint);
check2[FirstEndpoint]=cnt;
DistFromEndpoint[FirstEndpoint]=0;
Previ[FirstEndpoint]=-1;
CFurthest=0;
while(cur<clist.size()){
for(int k=0;k<adj[clist[cur]].size();k++){
if(!check2[adj[clist[cur]][k].first]){
clist.push_back(adj[clist[cur]][k].first);
DistFromEndpoint[adj[clist[cur]][k].first]=DistFromEndpoint[clist[cur]]+adj[clist[cur]][k].second;
Previ[adj[clist[cur]][k].first]=clist[cur];
if(DistFromEndpoint[adj[clist[cur]][k].first] > CFurthest){
CFurthest=DistFromEndpoint[adj[clist[cur]][k].first];
TreeRadius[cnt]=max(TreeRadius[cnt],CFurthest);
SecondEndpoint=adj[clist[cur]][k].first;
}
check2[adj[clist[cur]][k].first]=cnt;
}
}
cur++;
}
TreeDiameter[cnt]=CFurthest;
if(TreeRadius[cnt]!=0){
cur=SecondEndpoint;
while(cur>-1){
CMid=min(CMid,max(DistFromEndpoint[cur],DistFromEndpoint[SecondEndpoint]-DistFromEndpoint[cur]));
cur=Previ[cur];
}
TreeRadius[cnt]=CMid;
}
cnt++;
}
}
for(int i=1;i<cnt;i++){
TreeStats[i]={TreeRadius[i],TreeDiameter[i]};
}
sort(TreeStats+1,TreeStats+cnt, greater <pair <int,int> >());
//cout<<max(max())
int ans=0;
ans=TreeStats[1].second;
if(cnt>2){
ans=max(ans,TreeStats[1].first+TreeStats[2].first+len);
}
if(cnt>3){
ans=max(ans,TreeStats[2].first+TreeStats[3].first+len*2);
}
return ans;
}
Compilation message
dreaming.cpp: In function 'int travelTime(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
dreaming.cpp:46:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | while(cur<clist.size()){
| ~~~^~~~~~~~~~~~~
dreaming.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int k=0;k<adj[clist[cur]].size();k++){
| ~^~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:68:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | while(cur<clist.size()){
| ~~~^~~~~~~~~~~~~
dreaming.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int k=0;k<adj[clist[cur]].size();k++){
| ~^~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:88:77: warning: 'SecondEndpoint' may be used uninitialized in this function [-Wmaybe-uninitialized]
88 | CMid=min(CMid,max(DistFromEndpoint[cur],DistFromEndpoint[SecondEndpoint]-DistFromEndpoint[cur]));
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
/usr/bin/ld: /tmp/cc0xwdEC.o: in function `main':
grader.c:(.text.startup+0xd1): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
