| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1292614 | newsboy | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <chrono>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <utility>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
struct CD {
int n;
vector<int> siz, dep, parent, area;
vector<vector<int>> adj, lvl;
CD() {}
CD(int n) {
init(n);
}
void init(int n) {
this->n = n;
siz.resize(n);
dep.assign(n, -1);
parent.resize(n);
adj.assign(n, {});
area.resize(n);
lvl.clear();
}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void build(int u, int p = -1) {
siz[u] = 1;
for (auto v : adj[u]) {
if (v == p) {
continue;
}
if (dep[v] == -1) {
build(v, u);
siz[u] += siz[v];
}
}
}
int find(int u, int p, int tot) {
for (auto v : adj[u]) {
if (v == p) {
continue;
}
if (dep[v] == -1 && siz[v] * 2 > tot) {
return find(v, u, tot);
}
}
return u;
}
void work(int u = 0, int p = -1, int cur = 0) {
build(u);
int x = find(u, -1, siz[u]);
dep[x] = cur;
parent[x] = p;
if (lvl.size() == cur) {
lvl.push_back({});
}
lvl[cur].push_back(x);
area[x] = siz[u];
for (auto y : adj[x]) {
if (dep[y] == -1) {
work(y, x, cur + 1);
}
}
}
};
constexpr int inf = 1E9;
constexpr int K = 1E6;
vector<int> f(K + 1, inf);
int best_path(int n, int k, vector<array<int, 2>> edges, vector<int> t) {
f[0] = 0;
CD c(n);
vector<vector<array<int, 2>>> adj(n);
for (int i = 0; i < n - 1; i++) {
int u = edges[i][0], v = edges[i][1];
int w = t[i];
c.addEdge(u, v);
adj[u].push_back(array<int, 2>{v, w});
adj[v].push_back(array<int, 2>{u, w});
}
c.work();
int ans = inf;
for (int i = 0; i < c.lvl.size(); i++) {
for (auto x : c.lvl[i]) {
int need = c.dep[x];
vector<int> tot;
for (auto [y, w] : adj[x]) {
if (c.dep[y] < need) {
continue;
}
vector<array<int, 2>> cur;
auto dfs = [&](auto& self, int u, int p, int dis, int dep) -> void {
if (dis > k) {
return;
}
cur.push_back(array<int, 2>{dis, dep});
for (auto [v, w] : adj[u]) {
if (v == p) {
continue;
}
if (c.dep[v] > need) {
self(self, v, u, dis + w, dep + 1);
}
}
};
dfs(dfs, y, x, w, 1);
for (auto [dis, dep] : cur) {
ans = std::min(ans, f[k - dis] + dep);
if (f[dis] == inf) {
tot.push_back(dis);
}
f[dis] = std::min(f[dis], dep);
}
}
for (auto x : tot) {
f[x] = inf;
}
}
}
if (ans == inf) {
ans = -1;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<array<int, 2>> edges(n - 1);
vector<int> c(n - 1);
for (int i = 0; i < n - 1; i++) {
cin >> edges[i][0] >> edges[i][1] >> c[i];
}
cout << best_path(n, k, edges, c) << '\n';
}