| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1088773 | Persia | 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.
/*
Author: Persia
Date: 2024-09-14 09:00:14
*/
#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define rep2(i, l, r) for(int i = l; i >= r; i--)
#define fi first
#define se second
#define bit(i, x) (x >> i & 1)
using namespace std;
const int N = 2e5 + 3;
const int mod = 1e9 + 7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long rnd(long long l, long long r) {
return uniform_int_distribution<long long>(l, r)(rng);
}
int n, k;
vector<pair<int, int>> G[N];
int sz[N], deleted[N];
pair<long long, long long> d[N];
int in[N], out[N], rn[N], cnt;
pair<long long, long long> f[N][19];
int LG;
vector<array<long long, 3>> X;
pair<long long, long long> result = make_pair(1e18, 1e18);
void CalcSize(int u, int par) {
sz[u] = 1;
for(auto [v, w] : G[u]) if(v != par and !deleted[v]) {
CalcSize(v, u);
sz[u] += sz[v];
}
}
int FindCentroid(int u, int par, int nn) {
for(auto [v, w] : G[u]) if(v != par and !deleted[v]) {
if(sz[v] > nn / 2) return FindCentroid(v, u, nn);
}
return u;
}
void CalcCentroid(int u, int par) {
in[u] = ++cnt;
rn[cnt] = u;
for(auto [v, w] : G[u]) if(v != par and !deleted[v]) {
d[v] = {d[u].fi + w, d[u].se + 1};
CalcCentroid(v, u);
}
out[u] = cnt;
}
pair<long long, long long> Combine(const pair<long long, long long> &x, const pair<long long, long long> &y) {
pair<long long, long long> z;
if(x.fi != y.fi) z = min(x, y);
else z = make_pair(x.fi, x.se + y.se);
assert(z.fi >= 0);
// assert(z.se >= 1);
return z;
}
void SParseTable(vector<array<long long, 3>> &X) {
int sz = (int)X.size();
LG = 31 - __builtin_clz(sz);
assert(LG <= 18);
// assert(LG == (int)log2(sz));
rep(i, 0, sz - 1) f[i][0] = {X[i][2], 1};
rep(j, 1, LG) {
rep(i, 0, sz - 1 - (1 << (j - 1))) {
f[i][j] = Combine(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
// assert(i + (1 << j) - 1 <= sz - 1);
// assert(f[i][j].se >= 1);
}
}
}
pair<long long, long long> Query(int u, int v) {
if(u > v) return make_pair(1e18 + 1, 1e18 + 1);
int lg = 31 - __builtin_clz(v - u + 1);
assert(u >= 0 && u < (int)X.size());
assert(v < (int)X.size());
assert(lg <= LG);
assert(u + (1 << lg) - 1 <= (int)X.size() - 1);
return Combine(f[u][lg], f[v - (1 << lg) + 1][lg]);
}
void UpdateResult(pair<long long, long long> x, int z) {
x.fi += z;
if(x.fi < result.fi) result = {x.fi, x.se};
else if(x.fi == result.fi) result.se += x.se;
}
void Centroid(int u) {
CalcSize(u, -1);
u = FindCentroid(u, -1, sz[u]);
deleted[u] = 1;
// cerr << u << " ";
d[u] = {0, 0};
cnt = 0;
X.clear();
CalcCentroid(u, -1);
// rep(i, 1, n) {
// cerr << d[i].fi << " " << d[i].se << "\n";
// }
X.push_back({d[u].fi, 0, d[u].se});
for(auto [v, w] : G[u]) if (!deleted[v]) {
rep(i, in[v], out[v]) X.push_back({d[rn[i]].fi, v, d[rn[i]].se});
}
sort(X.begin(), X.end());
SParseTable(X);
for(auto [x, y, z] : X) {
// cerr << x << " " << y << " " << z << "\n";
array<long long, 3> target = {k - x, -1, -1};
int L = lower_bound(X.begin(), X.end(), target) - X.begin();
target = {k - x + 1, -1, -1};
int R = lower_bound(X.begin(), X.end(), target) - X.begin();
if(L != R) {
// cerr << L << " " << R << "\n";
// rep(i, L, R - 1) {
// assert(X[i][0] == k - x);
// if(X[i][1] != y) {
// UpdateResult(make_pair(X[i][2], 1), z);
// }
// }
target = {k - x, y, -1};
int l = lower_bound(X.begin(), X.end(), target) - X.begin();
target = {k - x, y + 1, -1};
int r = lower_bound(X.begin(), X.end(), target) - X.begin();
if(l != r) {
assert(L < R);
assert(l < r);
assert(l >= L);
assert(r <= R);
if(L <= l - 1) UpdateResult(Query(L, l - 1), z);
if(r <= R - 1) UpdateResult(Query(r, R - 1), z);
}
else {
if(L <= R - 1) UpdateResult(Query(L, R - 1), z);
}
}
}
for(auto [v, w] : G[u]) if (!deleted[v]) {
Centroid(v);
}
}
namespace BruteForce{
pair<long long, long long> result = make_pair(1e18, 1e18);
void DFS(int u, int par, pair<long long, long long> dist) {
if(dist.fi == k) {
if(dist.se < result.fi) result = {dist.se, 1};
else if(dist.se == result.fi) result.se++;
}
for(auto i : G[u]) if(i.fi != par) {
int v = i.fi, w = i.se;
DFS(v, u, make_pair(dist.fi + w, dist.se + 1));
}
}
int Solution() {
rep(i, 1, n) DFS(i, -1, make_pair(0, 0));
if(result.se == 1e18) result.se = -1;
return result.fi;
}
}
int main(int argc, char* argv[]) {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if(fopen("testing.txt", "r")) {
freopen("testing.txt", "r", stdin);
// freopen("outputing.txt", "w", stdout);
}
cin >> n >> k;
rep(i, 1, n - 1) {
int u, v, w; cin >> u >> v >> w;
u++, v++;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
// cout << BruteForce::Solution();
Centroid(1);
if(result.fi == 1e18) result.fi = -1;
cout << result.fi;
}