| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 873244 | wibulord | 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("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
#define db long double
#define fi first
#define se second
#define pb emplace_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pli pair<ll, int>
#define pdd pair<db, db>
#define iii pair<int, pair<int, int> >
#define ms(s, n) memset(s, n, sizeof(s))
#define all(a) a.begin(), a.end()
#define uni(a) (sort(all(a)), a.resize(unique(all(a))-a.begin()))
#define sz(a) int((a).size())
#define bit(x) bitset<10>((x))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (1 &((x) >> (i)))
#define clz(x) __builtin_clz((x))
#define ctz(x) __builtin_ctz((x))
#define popc(x) __builtin_popcount((x))
#define clzll(x) __builtin_clzll((x))
#define ctzll(x) __builtin_ctzll((x))
#define popcll(x) __builtin_popcountll((x))
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define F0R(i, b) for (int i = 0, _b = (b); i < _b; ++i)
#define FORd(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define F0Rd(i, b) for (int i = (b)-1; i >= 0; i--)
using namespace std;
template<typename T1,typename T2> bool ckmax(T1 &x,const T2 &y){if(x<y){x=y; return 1;} return 0;}
template<typename T1,typename T2> bool ckmin(T1 &x,const T2 &y){if(y<x){x=y; return 1;} return 0;}
const int MOD = 1000000007;
const int mod = 998244353;
const int oo = 1061109567;
const long long INF = 4557430888798830399;
const double PI = acos(-1);
const int N = 2e5 + 1, M = 19;
/*
/\_/\
(= ._.)
/ >? \>$
*/
int n, k, res;
vector<pair<int, int>> adj[N];
map<ll, int> mp[N];
ll dist[N], h[N];
void DFS(int u, int p = -1){
for(auto [v, c]: adj[u]) if(v != p){
dist[v] = dist[u] + c;
h[v] = h[u] + 1;
DFS(v, u);
}
mp[u][dist[u]] = h[u];
}
void dfs(int u, int p = -1){
for(auto [v, c] : adj[u]) if(v != p){
dfs(v, u);
if(sz(mp[v]) > sz(mp[u])) swap(mp[u], mp[v]);
for(auto [s, d] : mp[v]){
if(mp[u].find(k + 2*dist[u] - s) != mp[u].end()) ckmin(res, mp[u][k+2*dist[u]-s] + d - 2*h[u]);
}
for(auto [s, d] : mp[v]){
if(mp[u].find(s) == mp[u].end()) mp[u].insert({s, d});
else ckmin(mp[u][s], d);
}
}
}
void sol(){
cin >> n >> k;
F0R(i, n-1){
int u, v, w; cin >> u >> v >> w;
++u; ++v;
adj[u].pb(v, w); adj[v].pb(u, w);
}
res = 1e9;
DFS(1); dfs(1);
cout << (res == 1e9 ? -1 : res) << endl;
}
signed main(){
#define TASK "nhap"
if(fopen(TASK".inp", "r")){
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
fast; int t = 1;
// cin >> t;
while(t--) sol();
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms\n";
}