| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 43117 | aquablitz11 | Race (IOI11_race) | C++11 | 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.
// headers
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// types
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using dbl = double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
// loops
#define forx(i, x, y) for (int i = (x); i <= (y); ++i)
#define forn(i, n) for (int i = 0; i < (n); ++i)
#define for1(i, n) for (int i = 1; i <= (n); ++i)
#define rofx(i, x, y) for (int i = x; i >= y; --i)
#define rofn(i, n) for (int i = n-1; i >= 0; --i)
#define rof1(i, n) for (int i = n; i >= 1; --i)
#define fora(x, v) for (auto x : v)
// define shortcuts
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define X first
#define Y second
#define MP make_pair
#define MT make_tuple
// functions
template<class T> inline bool hasbit(T x, int i) { return x&(1<<i); }
template<class T> inline T togbit(T x, int i) { return x|(1<<i); }
template<class T> inline T setbit(T x, int i) { return x|(1<<i); }
template<class T> inline T rembit(T x, int i) { return x&~(1<<i); }
template<class T> inline bool setmax(T &a, const T &b) { return b > a ? a = b, true : false; }
template<class T> inline bool setmin(T &a, const T &b) { return b < a ? a = b, true : false; }
template<class T> int compress(vector<T> &v) { sort(all(v)); v.resize(unique(all(v))-v.begin()); return v.size(); }
// read functions
int read_int() { int x; scanf("%d", &x); return x; }
ll read_ll() { ll x; scanf("%" SCNd64, &x); return x; }
ull read_ull() { ull x; scanf("%" SCNu64, &x); return x; }
int read_dbl() { dbl x; scanf("%lf", &x); return x; }
void _R(int &x) { x = read_int(); }
void _R(ll &x) { x = read_ll(); }
void _R(dbl &x) { x = read_dbl(); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
// print functions
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const ll &x) { printf("%" PRId64, x); }
void _W(const ull &x) { printf("%" PRIu64, x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
// pseudo-random number generator
template<class T, T x1, T x2, T x3, int y1, int y2, int y3>
struct PRNG {
using S = typename make_signed<T>::type;
T s;
PRNG(T _s = 0) : s(_s) {}
T next() {
T z = (s += x1);
z = (z ^ (z >> y1)) * x2;
z = (z ^ (z >> y2)) * x3;
return z ^ (z >> y3);
}
T next(T n) { return next() % n; }
S next(S l, S r) { return l + next(r - l + 1); }
T operator()() { return next(); }
T operator()(T n) { return next(n); }
S operator()(S l, S r) { return next(l, r); }
static T gen(T s) { return PRNG(s)(); }
template<class U>
void shuffle(U first, U last) {
size_t n = last - first;
for (size_t i = 0; i < n; i++) swap(first[i], first[next(i + 1)]);
}
};
PRNG<uint32_t, 0x9E3779B1, 0x85EBCA6B, 0xC2B2AE35, 16, 13, 16> r32;
PRNG<uint64_t, 0x9E3779B97F4A7C15, 0xBF58476D1CE4E5B9, 0x94D049BB133111EB, 30, 27, 31> r64;
// program
int _main();
int main() {
//ios::sync_with_stdio(false), cin.tie(0);
//time_t begin = clock();
int ret = _main();
//time_t end = clock();
//fprintf(stderr, "Program took %.3f seconds to compute\n", ((double)end-begin)/CLOCKS_PER_SEC);
return ret;
}
/************************************************************
CODE STARTS BELOW THIS POINT
************************************************************/
const int INF = 1e9;
const int N = 2e5+10;
const int K = 1e6+10;
int n, k;
vector<pii> G[N];
int size[N], mx[N], par[N];
bool rem[N];
void calc_size(int u, int p=-1)
{
par[u] = p;
mx[u] = 0;
size[u] = 1;
fora(v, G[u]) if (v.F != p && !rem[v.F]) {
calc_size(v.F, u);
setmax(mx[u], size[v.F]);
size[u] += size[v.F];
}
}
int find_centroid(int s)
{
calc_size(s);
pii best(INF, s);
queue<int> Q;
Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
int sz = max(mx[u], size[s]-size[u]);
setmin(best, pii(sz, u));
fora(v, G[u]) if (v.F != par[u] && !rem[v.F])
Q.push(v.F);
}
return best.S;
}
unordered_map<int, int> new_path;
void find_path(int u, int p, int l, int sum)
{
if (sum > k) return;
if (!new_path[sum])
new_path[sum] = INF;
setmin(new_path[sum], l);
fora(v, G[u]) if (v.F != p && !rem[v.F])
find_path(v.F, u, l+1, sum+v.S);
}
int ans = INF;
int list_path[K];
void solve_tree(int u)
{
fora(v, G[u]) if (!rem[v.F]) {
find_path(v.F, u, 1, v.S);
fora(p, new_path) {
if (p.F == k)
setmin(ans, p.S);
setmin(ans, list_path[k-p.F]+p.S);
}
fora(p, new_path) {
setmin(list_path[p.F], p.S);
}
new_path.clear();
}
}
void recur(int u)
{
u = find_centroid(u);
solve_tree(u);
rem[u] = true;
fora(v, G[u]) if (!rem[v.F])
recur(v.F);
}
int best_path(int _N, int _K, int H[][2], int L[])
{
n = _N, k = _K;
forx(i, 0, k)
list_path[i] = INF;
forn(i, n-1) {
int u = H[i][0], v = H[i][1], w = L[i];
G[u].eb(v, w);
G[v].eb(u, w);
}
recur(0);
if (ans == INF)
ans = -1;
return ans;
}
int h[N][2], l[N];
int _main()
{
int n, k;
R(n, k);
forn(i, n-1)
R(h[i][0], h[i][1], l[i]);
W(best_path(n, k, h, l));
return 0;
}