#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int N = 1e5;
struct Graph {
vector<vector<pair<int, int>>> g;
vector<int> dp1, dp2, res;
int x;
vector<int> node;
vector<array<int, 3>> edges;
Graph() {
g.resize(N);
dp1.resize(N);
dp2.resize(N);
res.resize(N);
x = 0;
}
void add(int a, int b, int w) {
if (g[a].empty()) node.push_back(a);
if (g[b].empty()) node.push_back(b);
x = a;
g[a].push_back({b, w});
g[b].push_back({a, w});
edges.push_back({a, b, w});
}
void dfs1(int u, int p) {
dp1[u] = dp2[u] = 0;
for (auto [v, w] : g[u]) {
if (v == p) continue;
dfs1(v, u);
if (dp1[v] + w >= dp1[u]) {
dp2[u] = dp1[u];
dp1[u] = dp1[v] + w;
}
else {
dp2[u] = max(dp2[u], dp1[v] + w);
}
}
res[u] = max(res[u], dp1[u]);
}
void dfs2(int u, int p, int d) {
res[u] = max(res[u], d);
for (auto [v, w] : g[u]) {
if (v == p) continue;
int k = 0;
if (dp1[v] + w == dp1[u]) {
k = dp2[u];
}
else {
k = dp1[u];
}
dfs2(v, u, max(k, d) + w);
}
}
void process() {
dfs1(x, -1);
dfs2(x, -1, 0);
}
int findmin() {
process();
int mn = 1e9;
for (auto u : node) {
mn = min(mn, res[u]);
}
for (auto u : node) {
if (res[u] == mn) {
return u;
}
}
return 0;
}
void clear() {
for (auto u : node) {
g[u].clear();
dp1[u] = dp2[u] = res[u] = 0;
}
node.clear();
edges.clear();
x = 0;
}
};
vector<pair<int, int>> adj[N];
Graph tmp;
Graph res;
bool first = 1;
bool vis[N];
void dfs(int u) {
vis[u] = 1;
for (auto [v, w] : adj[u]) {
if (!vis[v]) {
if (first) {
res.add(u, v, w);
}
else {
tmp.add(u, v, w);
}
dfs(v);
}
}
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
vector<bool> is(n);
for (int i = 0; i < m; i++) {
int u = a[i], v = b[i], w = t[i];
is[u] = is[v] = 1;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
for (int i = 0; i < n; i++) {
if (!vis[i] && is[i]) {
tmp.clear();
dfs(i);
if (!first) {
res.add(res.findmin(), tmp.findmin(), l);
for (auto [u, v, w] : tmp.edges) {
res.add(u, v, w);
}
}
first = 0;
}
}
vector<int> v;
for (int i = 0; i < n; i++) {
if (!is[i]) {
int x = res.findmin();
res.add(x, i, l);
}
}
res.process();
int ans = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, res.res[i]);
}
return ans;
}
# | 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... |