| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 572120 | stevancv | 꿈 (IOI13_dreaming) | C++14 | 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.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
int mod = 1000000007;
vector<array<int, 2>> g[N];
bool was[N];
int up[N], down[N];
vector<int> v;
void Dfs(int s) {
was[s] = 1;
v.push_back(s);
for (auto u : g[s]) {
if (was[u[0]] == 0) {
Dfs(u[0]);
smax(down[s], down[u[0]] + u[1]);
}
}
}
void Dfs1(int s, int di) {
was[s] = 1;
up[s] = di;
int mx1, mx2;
mx1 = mx2 = 0;
for (auto u : g[s]) {
if (was[u[0]] == 0) {
if (down[u[0]] > mx1) {
mx2 = mx1;
mx1 = down[u[0]] + u[1];
}
else smax(mx2, down[u[0]] + u[1]);
}
}
for (auto u : g[s]) {
if (was[u[0]] == 0) {
if (down[u[0]] + u[1] == mx1) Dfs1(u[0], max(di, mx2) + u[1]);
else Dfs1(u[0], max(di, mx1) + u[1]);
}
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
for (int i = 0; i < m; i++) {
g[a[i]].push_back({b[i], t[i]});
g[b[i]].push_back({a[i], t [i]});
}
int ans = 0;
vector<int> svi;
for (int i = 0; i < n; i++) {
if (was[i] == 0) {
Dfs(i);
for (int j : v) was[j] = 0;
Dfs1(i, 0);
int koji = 1e9;
for (int j : v) {
int x = max(up[j], down[j]);
smax(ans, x);
smin(koji, x);
}
v.clear();
svi.push_back(koji);
}
}
sort(svi.rbegin(), svi.rend());
if (svi.size() >= 2) smax(ans, svi[0] + svi[1] + l);
if (svi.size() >= 3) smax(ans, svi[1] + svi[2] + 2 * l);
return ans;
}