| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1353758 | Chinguun | 경주 (Race) (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
#define ppb pop_back
#define meta int tm = (tl + tr) / 2, x = i * 2 + 1, y = x + 1
const int N = 2e5 + 7;
const int TN = 4 * N;
const int oo = 1e18;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
int n, k, p[30][N], d[30][N], lvl[N], mn = oo, pw[30];
vii v[N];
void dfs (int o, int par) {
for (auto c : v[o]) {
if (c.ff == par) continue;
lvl[c.ff] = lvl[o] + 1;
p[0][c.ff] = o;
d[0][c.ff] = c.ss;
dfs(c.ff, o);
}
}
pii distance (int x, int y) {
if (lvl[x] > lvl[y])
swap(x, y);
int d1 = 0, d2 = 0;
for (int i = 20; i >= 0; i--) {
if (lvl[y] - lvl[x] >= pw[i]) {
d1 += d[i][y];
d2 += pw[i];
y = p[i][y];
}
}
for (int i = 20; i >= 0; i--) {
if (p[i][x] != p[i][y]) {
d1 += d[i][x] + d[i][y];
d2 += pw[i] + pw[i];
x = p[i][x];
y = p[i][y];
}
}
if (x != y) {
d1 += d[0][x] + d[0][y];
d2 += 2;
}
return {d1, d2};
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> k;
pw[0] = 1;
for (int i = 1; i <= 20; i++)
pw[i] = pw[i - 1] * 2;
for (int i = 1; i < n; i++) {
int x, y, z;
cin >> x >> y >> z;
v[x].pb({y, z});
v[y].pb({x, z});
}
dfs(0, 0);
for (int i = 1; i <= 20; i++) {
for (int j = 0; j < n; j++) {
p[i][j] = p[i - 1][p[i - 1][j]];
d[i][j] = d[i - 1][j] + d[i - 1][p[i - 1][j]];
}
}
// cout << distance(1, 2).ff << '\n';
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
pii pr = distance(i, j);
// cout << i << ' ' << j << ' ' << pr.ff << '\n';
if (pr.ff == k) {
if (pr.ss < mn) mn = pr.ss;
}
}
}
if (mn == oo) cout << "-1";
else cout << mn;
return 0;
}