| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 857828 | sleepntsheep | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
using namespace std;
#define ALL(x) x.begin(), x.end()
#define N 200005
#define K 1000005
int n, k, sz[N], dead[N], z = 1e9, dp[K];
vector<pair<int, int>> g[N];
vector<int> accessed;
int dfs(int u, int p)
{
sz[u] = 1;
for (auto [w, v] : g[u]) if (v != p && !dead[v]) sz[u] += dfs(v, u);
return sz[u];
}
int get_centroid(int u, int p, int tn)
{
for (auto [w, v] : g[u]) if (v != p && !dead[v] && sz[v] * 2 >= tn) return get_centroid(v, u, tn);
return u;
}
void count(int u, int p, int fil, int dis, int dep)
{
if (dis > k) return;
accessed.push_back(dis);
if (fil) dp[dis] = min(dp[dis], dep);
else z = min(z, dp[k-dis] + dep);
for (auto [w, v] : g[u])
if (v != p && !dead[v]) count(v, u, fil, dis+w, dep+1);
}
void decomp(int u)
{
u = get_centroid(u, -1, dfs(u, -1));
dead[u] = 1;
dp[0] = 0;
for (auto [w, v] : g[u]) if (!dead[v]) count(v, u, 0, w, 1), count(v, u, 1, w, 1);
for (auto x : accessed) dp[x] = 1e9+40;
accessed.clear();
for (auto [w, v] : g[u]) if (!dead[v]) decomp(v);
}
int best_path(int n0, int k0, vector<vector<int>> h, vector<int> l)
{
memset(dp, 63, sizeof dp);
for (int i = 0; i < h.size(); ++i)
{
int u = h[i][0], v = h[i][1], w=l[i];
g[u].emplace_back(w, v), g[v].emplace_back(w, u);
}
decomp(0);
return (z < 1e9) ? z : -1;
}