| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 280141 | Kastanda | Dreaming (IOI13_dreaming) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// M
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 100005;
int n, m, L, D[3][N], M[N];
vector < pair < int , int > > Adj[N];
vector < int > vec;
void DFS(int v, int p, int w)
{
M[v] = 1;
if (w == 0)
vec.push_back(v);
for (auto u : Adj[v])
if (u.first != p)
D[w][u.first] = D[w][v] + u.second, DFS(u.first, v, w);
}
int travelTime(int _n, int _m, int _L, vector < int > A, vector < int > B, vector < int > W)
{
n = _n; m = _m; L = _L;
for (int i = 0; i < m; i ++)
{
Adj[A[i]].push_back({B[i], W[i]});
Adj[B[i]].push_back({A[i], W[i]});
}
vector < int > V;
for (int i = 0; i < n; i ++)
if (!M[i])
{
vec.clear();
DFS(i, -1, 0);
int d1 = i;
for (int v : vec)
if (D[0][v] > D[0][d1])
d1 = v;
DFS(d1, -1, 1);
int d2 = i;
for (int v : vec)
if (D[1][v] > D[1][d2])
d2 = v;
DFS(d2, -1, 2);
int Mn = D[1][d2];
for (int v : vec)
Mn = min(Mn, max(D[1][v], D[2][v]));
V.push_back(Mn);
}
sort(V.begin(), V.end());
reverse(V.begin(), V.end());
int Mx = V[0];
if ((int)V.size() > 1)
Mx = max(Mx, V[0] + V[1] + L);
if ((int)V.size() > 2)
Mx = max(Mx, V[1] + V[2] + L * 2);
return Mx;
}