| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 936991 | vjudge1 | 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.
//starting with the name of almighty ALLAH
// Practice is the only shortcut to improve
#include<bits/stdc++.h>
#include "race.h"
#define ll long long
#define pb push_back
#define vc vector
#define vi vc<int>
#define vl vc<ll>
#define mp(x,y) make_pair(x,y)
#define yes cout<<"YES"<<'\n';
#define no cout<<"NO"<<'\n';
#define tst int t;cin>>t;while(t--)
#define srt(v) sort(v.begin(),v.end());
#define rsrt(v) sort(v.rbegin(),v.rend());
#define rj ios::sync_with_stdio(false);cin.tie(0);
#define rvs(v) reverse(v.begin(),v.end());
#define F first
#define S second
#define MOD 1000000007
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*b)/gcd(a,b)
#define PI 2*acos(0.0)
#define pii pair<int,int>
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define coutv(v) for(auto it:v)cout<<it<<' ';cout<<endl;
#define cinv(v) for(auto &it:v)cin>>it;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define ld long double
#define nl '\n'
using namespace std;
/* #ifndef ONLINE_JUDGE
#include "algo/debug.h"
#else
#define dbg(x...)
#endif */
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int my_rand(int l, int r)
{
return uniform_int_distribution<int>(l, r) (rng);
}
const int N = 2e5 + 2;
vector<pii>adj[N];
int a, b;
bool done[N];
int sz[N];
int cur_subtree_size;
void set_subtree_size(int n, int p)
{
sz[n] = 1;
cur_subtree_size++;
for (auto it : adj[n])
{
if (it.F == p || done[it.first])
continue;
set_subtree_size(it.F, n);
sz[n] += sz[it.first];
}
}
int get_centroid(int n, int p)
{
for (auto it : adj[n])
{
if (it.first == p || done[it.first])
continue;
if (sz[it.first] > cur_subtree_size / 2)
return get_centroid(it.first, n);
}
return n;
}
int an;
map<int, int>save;
void dfs(int n, int p, int lvl, int q, int lv = 0)
{
if (lvl > b)
return;
if (q)
{
if (save.find(b - lvl) != save.end())
{
an = min(an, lv + save[b - lvl]);
return;
}
}
else {
if (save.find(lvl) != save.end())
{
save[lvl] = min(save[lvl], lv);
}
else
save[lvl] = lv;
}
for (auto it : adj[n])
{
if (it.first == p or done[it.first])
continue;
dfs(it.first, n, lvl + it.second, q, lv + 1);
}
}
void decompose(int n)
{
cur_subtree_size = 0;
set_subtree_size(n, -1);
int centroid = get_centroid(n, -1);
save[0] = 0;
for (auto it : adj[n])
{
if (!done[it.first])
{
dfs(it.first, centroid, 0, 1);
dfs(it.first, centroid, 0, 0);
}
}
save.clear();
done[centroid] = 1;
for (auto it : adj[centroid])
{
if (done[it.first])
continue;
decompose(it.first);
}
}
int best_path(int N, int K, int H[][2], int L[])
{
for (int i = 0; i < N - 1; i++)
{
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
a = N;
b = K;
an = INT_MAX;
decompose(0);
if (an == INT_MAX)
an = -1;
return an;
}
void solve()
{
{
cin >> a >> b;
int H[a][2], L[a];
for (int i = 0; i < a - 1; i++)
{
cin >> H[i][0] >> H[i][1] >> L[i];
}
cout << best_path(a, b, H, L) << nl;
}
}
int main()
{
rj
//int t;cin>>t;fr(i,1,t) cout<<"Case "<<i<<": ",solve();
//ll t;scanf("%lld",&t);fr(i,1,t) printf("Case %lld: ",i),solve();
solve();
return 0;
}