| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 203911 | kimjg1119 | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <random>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define ends " "
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define fio() ios_base::sync_with_stdio(0); cin.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-10;
int n, k, ans = INF;
int siz[202020], chk[202020];
vector<pii> adj[202020];
int find_size(int x, int par) {
int ret = 1;
for (auto th : adj[x]) {
if (th.first == par || chk[th.first]) continue;
ret += find_size(th.first, x);
}
return siz[x] = ret;
}
int get_cent(int x, int par, int cnt) {
for (auto th : adj[x]) {
if (th.first == par || chk[th.first]) continue;
if (siz[th.first] > cnt / 2) return get_cent(th.first, x, cnt);
}
return x;
}
vector<pii> all_path;
void find_path(int x, int par, int len, int dep) {
if (len > k) return;
all_path.emplace_back(len, dep);
for (auto th : adj[x]) {
if (th.first == par || chk[th.first]) continue;
find_path(th.first, x, len + th.second, dep + 1);
}
}
void solve(int x) {
int cal = find_size(x, x);
int cent = get_cent(x, x, cal);
// cent를 지나는 경로들
all_path.clear();
find_path(cent, cent, 0, 0);
sort(all(all_path));
vector<pii> path;
for (auto hr : all_path) {
if (!path.empty() && path.back().first == hr.first) continue;
path.push_back(hr);
}
int ri = sz(path) - 1;
for (int i = 0; i < ri; i++) {
int left = k - path[i].first;
while (ri > i + 1 && path[ri].first > left) ri--;
if (path[ri].first == left)
ans = min(ans, path[i].second + path[ri].second);
}
// cent를 지나지 않는 경로들
chk[cent] = 1;
for (auto th : adj[cent]) {
int thv = th.first;
if (chk[thv]) continue;
solve(thv);
}
}
int main() {
fio();
cin >> n >> k;
for (int i = 0; i < n - 1; i++) {
int a, b, t; cin >> a >> b >> t;
adj[a].emplace_back(b, t);
adj[b].emplace_back(a, t);
}
solve(0);
if (ans == INF) cout << -1;
else cout << ans;
return 0;
}