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;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
vector<vector<pair<int,int>>> arr(N);
for (int i = 0; i < M; i++){
arr[A[i]].push_back({B[i],T[i]});
arr[B[i]].push_back({A[i],T[i]});
}
int ans = 0;
vector<int> dp(N,-1);
function<int(int)> f = [&](int src)->int{
queue<array<int,3>> qu;
qu.push({src,0,-1});
int manode = src;
int mm = 0;
vector<int> gez;
while (qu.size()){
int node = qu.front()[0];
int w = qu.front()[1];
int lnode = qu.front()[2];
qu.pop();
if (w>mm) manode=node,mm=w;
for (auto nex : arr[node]){
if (nex.first==lnode) continue;
qu.push({nex.first,nex.second+w,node});
}
}
qu.push({manode,0,-1});
while (qu.size()){
int node = qu.front()[0];
int w = qu.front()[1];
int lnode = qu.front()[2];
qu.pop();
dp[node]=w;
ans=max(ans,w);
if (dp[node]>dp[manode]) manode=node;
for (auto nex : arr[node]){
if (nex.first==lnode) continue;
qu.push({nex.first,nex.second+w,node});
}
}
int ret = dp[manode];
qu.push({manode,0,-1});
while (qu.size()){
int node = qu.front()[0];
int w = qu.front()[1];
int lnode = qu.front()[2];
qu.pop();
ret=min(ret,max(dp[node],w));
for (auto &nex : arr[node]){
if (nex.first==lnode) continue;
qu.push({nex.first,nex.second+w,node});
}
}
return ret;
};
vector<int> ansarr;
for (int i = 0; i < N; ++i)
{
if (dp[i]==-1) {
ansarr.push_back(f(i));
}
}
if (ansarr.size()==1) return ans;
sort(ansarr.begin(), ansarr.end());
for (int i = 0; i < ansarr.size()-1; i++){
ansarr[i]+=L;
}
sort(ansarr.begin(), ansarr.end());
return max(ans,ansarr[ansarr.size()-1]+ansarr[ansarr.size()-2]);
}
Compilation message (stderr)
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int i = 0; i < ansarr.size()-1; 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... |