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 <stdio.h>
using namespace std;
vector < pair < int , int > > Next[100005];
vector < int > all;
bool have[100005]={0};
int a=0,b=0,c=0,t=0,big=0,bb=0,where;
void F(int here,int con)
{
all.push_back(here);
if(con>=big)
{
big=con;
where=here;
}
have[here]=1;
for(auto i:Next[here]) if(!have[i.first]) F(i.first,con+i.second);
}
void F2(int here,int Father,int con)
{
t=min(t,max(con,big-con));
for(auto i:Next[here]) if(i.first!=Father) F2(i.first,here,con+i.second);
}
void F3(int here,int Father,int con)
{
big=max(big,con);
for(auto i:Next[here]) if(i.first!=Father) F3(i.first,here,con+i.second);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
int i,how=0;
for(i=0;i<M;i++)
{
Next[A[i]].push_back(make_pair(B[i],T[i]));
Next[B[i]].push_back(make_pair(A[i],T[i]));
}
for(i=0;i<N;i++)
{
if(!have[i])
{
how++;
big=0;
where=0;
all.clear();
F(i,0);
t=1e9;
for(auto j:all)
{
big=0;
F3(i,-1,0);
t=min(t,big);
}
if(t>=a)
{
c=b;
b=a;
a=t;
}
else if(t>=b)
{
c=b;
b=t;
}
else if(t>=c) c=t;
}
}
if(how>=2) bb=max(bb,a+b+L);
if(how>=3) bb=max(bb,b+c+2*L);
return bb;
}
Compilation message (stderr)
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:49:22: warning: unused variable 'j' [-Wunused-variable]
49 | for(auto j:all)
| ^
# | 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... |