| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1231407 | rhm_gan | Dreaming (IOI13_dreaming) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const short N = 1e5;
struct Graph {
vector<vector<pair<short, short>>> g;
vector<short> dp1, dp2, res;
short x, cnt;
Graph() {
g.resize(N);
dp1.resize(N);
dp2.resize(N);
res.resize(N);
x = cnt = 0;
}
void add(short a, short b, short w) {
x = a;
g[a].push_back({b, w});
g[b].push_back({a, w});
cnt++;
}
void dfs1(short u, short p) {
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(short u, short p, short d) {
res[u] = max(res[u], d);
for (auto [v, w] : g[u]) {
if (v == p) continue;
short k = 0;
if (dp1[v] + w == dp1[u]) {
k = dp2[u];
}
else {
k = dp1[u];
}
dfs2(v, u, max(k, d) + w);
}
}
short findmin() {
dfs1(x, -1);
dfs2(x, -1, 0);
short mn = 1e9;
for (short i = 0; i < N; i++) {
if (res[i] != 0) {
mn = min(mn, res[i]);
}
}
for (short i = 0; i < N; i++) {
if (res[i] == mn) {
return i;
}
}
return -1;
}
bool empty() {
return cnt == 0;
}
void clear() {
g.assign(N, vector<pair<short, short>>());
dp1.assign(N, 0);
dp2.assign(N, 0);
res.assign(N, 0);
x = cnt = 0;
}
};
vector<pair<short, short>> adj[N];
vector<Graph> g;
Graph tmp;
bool vis[N];
void dfs(short u) {
vis[u] = 1;
for (auto [v, w] : adj[u]) {
if (!vis[v]) {
tmp.add(u, v, w);
dfs(v);
}
}
}
short travelTime(short n, short m, short l, short a[], short b[], short t[]) {
Graph res;
vector<bool> is(n);
for (short i = 0; i < m; i++) {
short 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});
res.add(u, v, w);
}
for (short i = 0; i < n; i++) {
if (!vis[i]) {
tmp.clear();
dfs(i);
g.push_back(tmp);
}
}
vector<short> v;
for (short i = 0; i < n; i++) {
if (!is[i]) {
v.push_back(i);
}
}
for (short i = 0; i < g.size(); i++) {
if (!g[i].empty()) {
v.push_back(g[i].findmin());
}
}
for (short i = 1; i < v.size(); i++) {
res.add(v[i], v[i - 1], l);
}
short id = res.findmin();
short ans = 0;
for (short i = 0; i < N; i++) {
ans = max(ans, res.res[i]);
}
return ans;
}