| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 706472 | Asamai | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template<class A, class B> bool maximize(A& x, B y) {if (x < y) return x = y, true; else return false;}
template<class A, class B> bool minimize(A& x, B y) {if (x > y) return x = y, true; else return false;}
#define all(a) a.begin(), a.end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
//#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
typedef pair<db, db> pdb;
typedef pair<ld, ld> pld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> plli;
typedef pair<int, ll> pill;
const int MAX_N = 2e5 + 5;
const int mod = 1e9 + 7; // 998244353
const int inf = 1e9 + 1;
int n, k;
vector<pii> adj[MAX_N];
bool processed[MAX_N];
int ans = inf;
int child[MAX_N];
int dfs(int u, int pr = 0) {
child[u] = 1;
for (auto it : adj[u]) {
int v = it.fi;
if (!processed[v] && v != pr) {
child[u] += dfs(v, u);
}
}
return child[u];
}
int find_centroid(int u, int pr, int sz) {
for (auto it : adj[u]) {
int v = it.fi;
if (!processed[v] && v != pr && child[v] > sz) {
return find_centroid(v, u, sz);
}
}
return u;
}
const int MAX_VAL = 1e6 + 10;
int dp[MAX_VAL];
vector<int> used;
void go_cal(int u, int pr, bool ok, int len, int dep) {
if (k < len) return;
if (ok) {
used.pb(len);
minimize(dp[len], dep);
}
else {
minimize(ans, dp[k - len] + dep);
}
for (auto it : adj[u]) {
int v = it.fi;
int w = it.se;
if (!processed[v] && v != pr) {
go_cal(v, u, ok, len + w, dep + 1);
}
}
}
void centroid_decomposition(int u) {
int c = find_centroid(u, 0, dfs(u) >> 1);
processed[c] = true;
used.clear();
dp[0] = 0;
for (auto it : adj[c]) {
int v = it.fi;
int w = it.se;
if (!processed[v]) {
go_cal(v, c, false, w, 1);
go_cal(v, c, true, w, 1);
}
}
for (auto it : used) {
dp[it] = inf;
}
for (auto it : adj[c]) {
int v = it.fi;
if (!processed[v]) {
centroid_decomposition(v);
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 0; i <= k; i ++) {
dp[i] = inf;
}
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
u++; v++;
adj[u].pb({v, w});
adj[v].pb({u, w});
}
centroid_decomposition(1);
cout << (ans == inf ? -1 : ans);
return 0;
}
/*
*/