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<iostream>
#include<algorithm>
using namespace std;
vector<pair<int,int > > g[200000];
int u[200000],x[200000],d[200000],pa[200000],mh,ind,t,pat;
void dfs(int v,int p)
{
u[v]=1;
for(int i=0;i<g[v].size();i++)
{
int to =g[v][i].first;
int her=g[v][i].second;
if(to==p)
continue;
d[to]=d[v]+ her;
pa[to]=v;
if(d[to]>mh)
{
mh=d[to];
ind=to;
}
dfs(to,v);
}
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
for(int i=0;i<M;i++)
{
g[A[i]].push_back(make_pair(B[i],T[i]));
g[B[i]].push_back(make_pair(A[i],T[i]));
}
for(int i=0;i<N;i++)
{
if(u[i]==0)
{
d[i]=0;
mh=0;
ind=i;
dfs(i,-1);
int a=ind;
d[a]=0;
mh=0;
ind=a;
dfs(a,-1);
int b=ind;
int e=b;
int l=mh;
while(e!=a)
{
l=min(l,max(mh-d[e],d[e]));
e=pa[e];
}
x[t]=l;
t++;
}
}
sort(x,x+t);
pat=max(pat,x[t-1]);
if(t>=2)
pat=max(pat,x[t-1]+x[t-2]+L);
if(t>=3)
pat=max(pat,x[t-2]+x[t-3]+2*L);
return pat;
}
Compilation message (stderr)
dreaming.cpp: In function 'void dfs(int, int)':
dreaming.cpp:11:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
# | 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... |