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 <iostream>
#include <algorithm>
#include "assert.h"
#define int int64_t
using namespace std;
struct graph
{
int n;
vector<vector<pair<int,int>>> adjlist;
vector<int> comp;
vector<int> dist;
int nrcomp = 0;
void compdfs(int curr, int par, int c)
{
comp[curr] = c;
for (auto p : adjlist[curr])
{
int next = p.first;
if (next == par) continue;
compdfs(next, curr, c);
}
}
void distdfs(int curr, int par, int d)
{
dist[curr] = max(dist[curr], d);
for (auto p : adjlist[curr])
{
int next = p.first;
int w = p.second;
if (next == par) continue;
distdfs(next, curr, d + w);
}
}
void print()
{
for (int i = 0; i < n; i++)
{
if (i < 10) cout << " ";
cout << i << " ";
}
cout << "\n";
for (auto i : dist)
{
if (i < 10) cout << " ";
cout << i << " ";
}
cout << "\n";
}
int calcdiameter(int st)
{
dist.assign(n, -1);
distdfs(st, -1, 0);
int mmax = -1;
int mver = -1;
for (int i = 0; i < n; i++)
{
if (dist[i] == -1) continue;
if (mmax < dist[i])
{
mmax = dist[i];
mver = i;
}
}
dist.assign(n, -1);
distdfs(mver, -1, 0);
return *max_element(dist.begin(), dist.end());
}
int calc(int l)
{
dist.resize(n, -1);
comp.resize(n, -1);
for (int i = 0; i < n; i++)
{
if (comp[i] == -1)
{
compdfs(i, -1, nrcomp);
nrcomp++;
}
}
if (nrcomp == 1)
{
return calcdiameter(0);
}
for (int i = 0; i < n; i++)
{
if (dist[i] < 0)
{
distdfs(i, -1, 0);
}
}
vector<int> md(nrcomp, -1);
vector<int> mv(nrcomp, -1);
for (int i = 0; i < n; i++)
{
if (dist[i] > md[comp[i]])
{
md[comp[i]] = dist[i];
mv[comp[i]] = i;
}
}
for (auto i : mv) distdfs(i, -1, 0);
md.assign(nrcomp, -1);
mv.assign(nrcomp, -1);
int mmax = 0;
for (int i = 0; i < n; i++)
{
mmax = max(mmax, dist[i]);
if (dist[i] > md[comp[i]])
{
md[comp[i]] = dist[i];
mv[comp[i]] = i;
}
}
for (auto i : mv) distdfs(i, -1, 0);
md.assign(nrcomp, 1e12);
for (int i = 0; i < n; i++)
{
if (dist[i] < md[comp[i]])
{
md[comp[i]] = dist[i];
}
}
sort(md.begin(), md.end());
mmax = max(mmax, md[nrcomp - 1] + md[nrcomp - 2] + l);
if (nrcomp != 2) mmax = max(md[nrcomp - 2] + md[nrcomp - 3] + 2*l, mmax);
return mmax;
}
};
signed travelTime(signed N, signed M, signed L, signed A[], signed B[], signed T[])
{
graph g;
g.n = N;
g.adjlist.resize(N);
for (int i = 0; i < M; i++)
{
g.adjlist[A[i]].emplace_back(B[i], T[i]);
g.adjlist[B[i]].emplace_back(A[i], T[i]);
}
return g.calc(L);
}
# | 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... |