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>
#define int long long
#define pri pair<int,int>
using namespace std;
struct node {
vector<pri> adj;
};
int32_t travelTime(int32_t N, int32_t M, int32_t L, int32_t A[], int32_t B[], int32_t T[]) {
vector<node> nodes(N);
for (int i = 0;i<M;i++) {
nodes[A[i]].adj.push_back({B[i],T[i]});
nodes[B[i]].adj.push_back({A[i],T[i]});
}
auto bfs = [nodes,N](int src) {
queue<int> q;q.push(src);
vector<int> trail(N,1e9);
vector<int> dist(N,-1);
trail[src]=-1;
dist[src]=0;
while (q.size()) {
auto f = q.front();
for (int i = 0;i<nodes[f].adj.size();i++) {
if (nodes[f].adj[i].first==trail[f]) continue;
trail[nodes[f].adj[i].first] = f;
dist[nodes[f].adj[i].first] = dist[f] + nodes[f].adj[i].second;
q.push(nodes[f].adj[i].first);
}
q.pop();
}
return pair<vector<int>,vector<int>>{dist,trail};
};
vector<int> visit(N,0);
vector<int> paths;
for (int i = 0;i<N;i++) {
if (visit[i]==1) continue;
auto res = bfs(i);
pri mxd = {-1,-1};
for (int j = 0;j<N;j++) {
if (res.second[j]!=1e9) visit[j]=1;
if (res.first[j] > mxd.first) {
mxd = {res.first[j],j};
}
}
auto res2 = bfs(mxd.second);
mxd = {-1,-1};
for (int j = 0;j<N;j++) {
if (res2.first[j] > mxd.first) {
mxd = {res2.first[j],j};
}
}
int tl = mxd.first;
int t = res2.second[mxd.second];
int mn = (t==-1)?0:1e9;
while (t!=-1) {
mn=min(mn,max(res2.first[t],tl-res2.first[t]));
t = res2.second[t];
}
paths.push_back(mn);
}
sort(paths.begin(),paths.end());
if (paths.size()==1) return paths[0];
else if (paths.size()==2) return paths[1]+paths[0]+L;
else return max(paths[paths.size()-1]+paths[paths.size()-2]+L,paths[paths.size()-2]+paths[paths.size()-3]+2*L);
//return 12;
}
Compilation message (stderr)
dreaming.cpp: In lambda function:
dreaming.cpp:24:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for (int i = 0;i<nodes[f].adj.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... |