This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dreaming.h"
#include <vector>
#include <algorithm>
using namespace std;
static const int MAXN=100100;
static vector<pair<int,int> > conn[MAXN];
static int color[MAXN];
static int tp=0;
static int hdist[MAXN];
static int dist[MAXN];
static int parent[MAXN];
static vector<int> samecolor[MAXN];
static vector<int> radius;
void colordfs(int a,int pa,int c)
{
color[a]=c;
samecolor[c].push_back(a);
for(int i=0;i<conn[a].size();i++)
{
int target=conn[a][i].first;
if(target==pa) continue;
hdist[target]=hdist[a]+conn[a][i].second;
colordfs(target,a,c);
}
}
void dfs(int a,int pa)
{
parent[a]=pa;
for(int i=0;i<conn[a].size();i++)
{
int target=conn[a][i].first;
if(target==pa) continue;
dist[target]=dist[a]+conn[a][i].second;
dfs(target,a);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
tp=0;
radius.clear();
for(int i=0;i<MAXN;i++)
{
conn[i].clear();
color[i]=0;
hdist[i]=0;
dist[i]=0;
parent[i]=0;
samecolor[i].clear();
}
for(int i=0;i<M;i++)
{
conn[A[i]].push_back(make_pair(B[i],T[i]));
conn[B[i]].push_back(make_pair(A[i],T[i]));
}
for(int i=0;i<N;i++)
if(!color[i]) colordfs(i,-1,++tp);
int retval=0;
for(int i=1;i<=tp;i++)
{
int furthest=samecolor[i][0];
for(int j=0;j<samecolor[i].size();j++)
if(hdist[furthest]<hdist[samecolor[i][j]]) furthest=samecolor[i][j];
dfs(furthest,-1);
int dia=furthest;
for(int j=0;j<samecolor[i].size();j++)
if(dist[dia]<dist[samecolor[i][j]]) dia=samecolor[i][j];
int radii=dist[dia];
int res=radii;
retval=max(retval,radii);
while(dia!=-1)
{
res=min(res,max(radii-dist[dia],dist[dia]));
dia=parent[dia];
}
radius.push_back(res);
}
sort(radius.begin(),radius.end());
reverse(radius.begin(),radius.end());
if(tp==2) retval=max(retval, radius[0]+radius[1]+L);
else if(tp>2) retval=max(retval,max(radius[0]+radius[1]+L,radius[1]+radius[2]+2*L));
return retval;
}
Compilation message (stderr)
dreaming.cpp: In function 'void colordfs(int, int, int)':
dreaming.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<conn[a].size();i++)
~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:30:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<conn[a].size();i++)
~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<samecolor[i].size();j++)
~^~~~~~~~~~~~~~~~~~~~
dreaming.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<samecolor[i].size();j++)
~^~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |