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;
vector<pair<long long, long long> > adj[100005];
priority_queue<pair<long long, long long> > pq;
long long dist[100005], par[100005];
vector<long long> vec, tor, z;
bool visited[100005];
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
for (long long i=0; i<M; i++)
{
adj[A[i]].push_back({B[i], T[i]});
adj[B[i]].push_back({A[i], T[i]});
}
for (long long i=0; i<N; i++)
dist[i]=1e18;
long long mx=0;
for (long long i=0; i<N; i++)
{
if (visited[i])
continue;
long long x, y, cur, len=1e18;
dist[i]=0;
pq.push({0, i});
while (!pq.empty())
{
long long d=pq.top().first, u=pq.top().second;
pq.pop();
if (dist[u]!=-d)
continue;
vec.push_back(u);
visited[u]=1;
for (long long j=0; j<adj[u].size(); j++)
{
long long v=adj[u][j].first, w=adj[u][j].second;
if (dist[u]+w<dist[v])
{
dist[v]=dist[u]+w;
pq.push({-dist[v], v});
}
}
}
// cout << "vec: ";
// for (long long u:vec)
// cout << u << ' ';
// cout << '\n';
x=vec[0];
for (long long j=1; j<vec.size(); j++)
if (dist[x]<dist[vec[j]])
x=vec[j];
for (long long j=0; j<vec.size(); j++)
dist[vec[j]]=1e18;
// cout << "x=" << x << '\n';
dist[x]=0;
pq.push({0, x});
while (!pq.empty())
{
long long d=pq.top().first, u=pq.top().second;
pq.pop();
if (dist[u]!=-d)
continue;
for (long long j=0; j<adj[u].size(); j++)
{
long long v=adj[u][j].first, w=adj[u][j].second;
if (dist[u]+w<dist[v])
{
par[v]=u;
dist[v]=dist[u]+w;
pq.push({-dist[v], v});
}
}
}
y=vec[0];
for (long long j=1; j<vec.size(); j++)
if (dist[y]<dist[vec[j]])
y=vec[j];
// cout << "y=" << y << '\n';
cur=y;
while (cur!=x)
{
tor.push_back(cur);
cur=par[cur];
}
tor.push_back(x);
for (long long u:tor)
len=min(len, max(dist[u], dist[y]-dist[u]));
mx=max(mx, dist[y]);
z.push_back(len);
vec.clear();
tor.clear();
}
sort(z.begin(), z.end(), greater<long long>());
if (z.size()==1)
return mx;
else if (z.size()==2)
return max(mx, z[0]+z[1]+L);
else
return max(mx, max(z[0]+z[1]+L, z[1]+z[2]+L*2));
}
Compilation message (stderr)
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:34:34: 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]
34 | for (long long j=0; j<adj[u].size(); j++)
| ~^~~~~~~~~~~~~~
dreaming.cpp:49:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (long long j=1; j<vec.size(); j++)
| ~^~~~~~~~~~~
dreaming.cpp:52:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | for (long long j=0; j<vec.size(); j++)
| ~^~~~~~~~~~~
dreaming.cpp:63:34: 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]
63 | for (long long j=0; j<adj[u].size(); j++)
| ~^~~~~~~~~~~~~~
dreaming.cpp:75:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (long long j=1; j<vec.size(); j++)
| ~^~~~~~~~~~~
# | 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... |