#include<algorithm>
#include<vector>
using namespace std;
int N,M,L;
int Y[100010],tl,inl;
int tmp[100010],Q[100010][3];
int check[100010];
struct line{
line(){}
line(int en,int len):en(en),len(len){}
int en,len;
};
vector <line> edge[100010];
int far(int x)
{
int fr=1,re=0,ret=x,mx=0;
Q[0][0]=x;Q[0][1]=0;check[x]=1;
while(fr!=re){
int i;
for(i=0;i<edge[Q[re][0]].size();i++){
int tx=edge[Q[re][0]][i].en;
if(check[tx])continue;
check[tx]=1;
Q[fr][0]=tx;
Q[fr][1]=Q[re][1]+edge[Q[re][0]][i].len;
if(mx<Q[fr][1]){
mx=Q[fr][1];
ret=Q[fr][0];
}
fr++;
}
re++;
}
return ret;
}
void solve(int x)
{
int t=far(x),fr=1,re=0,tp=0;
Q[0][0]=t;Q[0][1]=0;Q[0][2]=-1;check[t]=2;
while(fr!=re){
int i;
for(i=0;i<edge[Q[re][0]].size();i++){
int tx=edge[Q[re][0]][i].en;
if(check[tx]==2)continue;
check[tx]=2;
Q[fr][0]=tx;
Q[fr][1]=Q[re][1]+edge[Q[re][0]][i].len;
Q[fr][2]=re;
if(Q[fr][1]>Q[tp][1])tp=fr;
fr++;
}
re++;
}
int len=Q[tp][1],tx=0;
while(Q[tp][2]!=-1){
if(Q[tp][1]*2>len)tx=Q[tp][1];
else{tx=min(tx,len-Q[tp][1]);break;}
tp=Q[tp][2];
}
Y[tl]=tx;tl++;
inl=max(inl,len);
}
int travelTime(int Nn, int Mm, int Ll, int A[], int B[], int T[]){
N=Nn,M=Mm,L=Ll;
int i;
for(i=0;i<M;i++){
edge[A[i]+1].push_back(line(B[i]+1,T[i]));
edge[B[i]+1].push_back(line(A[i]+1,T[i]));
}
for(i=1;i<=N;i++){
if(check[i])continue;
solve(i);
}
sort(Y,Y+tl);
if(tl==1)return inl;
if(tl==2)return max(inl,L+Y[tl-1]+Y[tl-2]);
else return max(inl,max(L+Y[tl-1]+Y[tl-2],2*L+Y[tl-2]+Y[tl-3]));
}
Compilation message
dreaming.cpp: In function 'int far(int)':
dreaming.cpp:22:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<edge[Q[re][0]].size();i++){
~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void solve(int)':
dreaming.cpp:45:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<edge[Q[re][0]].size();i++){
~^~~~~~~~~~~~~~~~~~~~~~
/tmp/ccXZ94zm.o: In function `main':
grader.c:(.text.startup+0xa2): undefined reference to `travelTime'
collect2: error: ld returned 1 exit status
