| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1089271 | RiverFlow | Race (IOI11_race) | C++14 | 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>
#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())
using namespace std;
template<typename U, typename V> bool maxi(U &a, V b) {
if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
if (a > b) { a = b; return 1; } return 0;
}
const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;
void prepare(); void main_code();
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
const bool MULTITEST = 0; prepare();
int num_test = 1; if (MULTITEST) cin >> num_test;
while (num_test--) { main_code(); }
}
void prepare(){};
int n, k;
vec<ii> g[N];
bool on[N];
int s[N];
void init(int u, int p) {
s[u] = 1;
for(auto [v,w] : g[u]) if (on[v] and v != p) {
init(v, u);
s[u] += s[v];
}
}
int centroid(int u, int p, int t) {
for(auto [v,w]:g[u])if(on[v] and v!=p and s[v]>t/2)
return centroid(v,u,t);
return u;
}
int ans = 0;
multiset<int> d[5 * N];
void DFS(int u, int par, bool t, int dis, int dx) {
if (dis > k) return ;
if (t == 0) {
if (sz(d[k - dis])) {
ans = min(ans, dx + *d[k - dis].begin());
}
} else if (t == 1) {
d[dis].insert(dx);
} else
d[dis].erase(d[dis].find(dx));
for(auto [v,w] : g[u]) if (v != par and on[v]) {
DFS(v, u, t, dis + w, dx + 1);
}
}
void calc(int u) {
d[0].insert(0);
for(auto [v,w] : g[u]) if (on[v]) {
DFS(v,u,0,w, 1);
DFS(v,u,1,w, 1);
}
for(auto [v,w] : g[u]) if (on[v]) {
DFS(v,u,-1,w, 1);
}
d[0].erase(0);
}
void solve(int u) {
init(u, 0);
u = centroid(u, 0, s[u]);
calc(u);
on[u] = 0;
for(auto [v,w] : g[u]) if (on[v]){
solve(v);
}
}
void main_code() {
cin >> n >> k;
ans = n + 1;
FOR(i, 1, n) on[i] = 1;
FOR(i, 2, n) {
int u, v, w; cin >> u >> v >> w;
++u, ++v;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
solve(1);
if (ans == n + 1) ans = -1;
cout << ans;
}
/* Let the river flows naturally */