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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5;
vector<pair<int,int>> g[maxn];
vector<int> C;
int mx,to,cst[maxn],t,best,mn,vis[maxn],c,ans;
void path(int u,int cost){
vis[u] = c;
if(cost > mx){
mx = cost;
to = u;
}
for(pair<int,int> cur : g[u]){
int v = cur.first;
int w = cur.second;
if(vis[v] == c)continue;
path(v,cost + w);
}
}
void dfs(int u,int cost){
vis[u] = c;
if(t == 1){
cst[u] = max(cst[u],cost);
if(cst[u] < mn){
mn = cst[u];
best = u;
}
}else cst[u] = cost;
for(pair<int,int> cur : g[u]){
int v = cur.first;
int w = cur.second;
if(vis[v] == c)continue;
dfs(v,cost + w);
}
}
void find(int s){
mn = 2e9;
mx = -1;
c++;
path(s,0);
int a = to;
c++;
mx = -1;
path(a,0);
int b = to;
t = 0;
c++;
dfs(a,0);
t = 1;
c++;
dfs(b,0);
ans = max(ans,mx);
C.push_back(mn);
}
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({B[i],T[i]});
g[B[i]].push_back({A[i],T[i]});
}
for(int i=0;i<N;i++)
if(!vis[i])
find(i);
sort(C.begin(),C.end());
reverse(C.begin(),C.end());
if(C.size() > 1){
ans = max(ans,C[0] + C[1] + L);
if(C.size() > 2)ans = max(ans,C[1] + C[2] + 2*L);
}
return ans;
}
# | 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... |