| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 906183 | MinhKhoi | 경주 (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.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long double ld;
typedef long long ll;
using namespace std;
const double eps = 1e-8;
const ll Base = 31;
const ll MAX = 1e6 + 2;
const ll Mod = 1e9 + 7;
const ll inf = 1e18;
const ll N = 2e5 + 10;
// VARIABLE
#define umap unordered_map
#define pque priority_queue
#define mset multiset
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define vI vector<int>
#define vL vector<ll>
#define mp make_pair
// SHORTCUTS
#define redup(s) sort(all(s)), (s).resize(unique(all(s)) - (s).begin())
#define all(s) s.begin(), s.end()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
// FUNCTIONS
#define fu(i, a, b) for(int i = a; i <= b; ++i)
#define fd(i, a, b) for(int i = a; i >= b; --i)
#define fe(i, adj) for(auto i : adj)
#define debug(...) " [" << #__VA_ARGS__ " = " << (__VA_ARGS__) << "] "
#define mask(s) (1LL << (s))
#define sz(s) (int) s.size()
#define fs(s) fixed << setprecision(s)
// TEMPLATE
template <class T>
bool minimize(T &x, T y){return (x > y ? x = y, 1 : 0);}
template <class T>
bool maximize(T &x, T y){return (x < y ? x = y, 1 : 0);}
template <class T>
void add(T &x, T y){x += y; if(x >= Mod) x -= Mod;}
template <class T>
void sub(T &x, T y){x -= y; if(x < 0) x += Mod;}
// CAL
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) (x) / gcd(x, y) * y
#define sqr(x) abs(x) * abs(x)
// BITWISE
#define bit(msk, i) (msk >> i) & 1
#define logOf(msk) 63 - clz(msk)
#define lbit(msk) ((msk) & (-msk))
#define cbit(msk) __builtin_popcountll(msk)
#define ctz(msk) __builtin_ctzll(msk)
#define clz(msk) __builtin_clzll(msk)
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1},
dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
/*
-----------------------------------------
🛸 🌎 ★ 🛰 ° 🚀 ✯
★ ° ☄ ✯ ★ ° 🪐
✯ 🚀 • 🌓 ° 🛰 • ☄
_________________________________________
*/
/// ===================================== - MAIN - ===================================== ///
#define File ""
int n, child[N];
bool vs[N];
ll k, ans = inf, weight = 0, cnt[MAX];
vector<pii> adj[N];
void dfs(int u, int p){
child[u] = 1;
fe(v, adj[u]) if(v.fi != p && !vs[v.fi]) dfs(v.fi, u), child[u] += child[v.fi];
}
int centroid(int u, int p, int cur){
fe(v, adj[u]) if(v.fi != p && !vs[v.fi] && (child[v.fi] << 1) > cur) return centroid(v.fi, u, cur);
return u;
}
void build(int u, int p, bool flag, ll cost, int depth = 2){
if(cost > k) return;
maximize(weight, cost);
if(flag) minimize(cnt[cost], 1LL * depth);
else{
minimize(ans, cnt[k - cost] + depth - 2);
}
fe(v, adj[u]) if(v.fi != p && !vs[v.fi]) build(v.fi, u, flag, cost + v.se, depth + 1);
}
void solve(int u){
dfs(u, 0);
int nxt = centroid(u, 0, child[u]);
weight = 0;
fe(v, adj[nxt]) if(!vs[v.fi]){
build(v.fi, nxt, false, v.se);
build(v.fi, nxt, true, v.se);
}
memset(cnt, 0x3f, (weight + 1) * sizeof(ll));
vs[nxt] = true;
fe(v, adj[nxt]) if(!vs[v.fi]) solve(v.fi);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
if(fopen(File".INP", "r")){
freopen(File".INP", "r", stdin); freopen(File".OUT", "w", stdout);
}
cin >> n >> k;
fu(i, 2, n){
int u, v, l; cin >> u >> v >> l;
adj[++u].pb(mp(++v, l)), adj[v].pb(mp(u, l));
}
//memset(cnt, 0x3f, (weight + 2) * sizeof(ll));
memset(cnt, 0x3f, sizeof(cnt));
solve(1);
cout << (ans == inf ? -1 : ans);
return 0;
}