| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1111085 | PhcKhnhTapCode | 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.
#include <bits/stdc++.h>
/**-----------------------------------------
------Author: PhcKhnhTapCode ---------------
------From: CHV with luv <3 ----------------
------Source:_________________--------------
---------//--------YAT---------//-----------
-----------------------------------------**/
using namespace std;
#define YAT "test"
#define db long double
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define pub push_back
#define ii pair<int, int>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define vii vector<ii>
#define all(v) v.begin(),v.end()
#define RESET(f, v) memset(f, v, sizeof f)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define FORV(v, H) for (auto &v: H)
#define BIT(n, i) ((n >> i) & 1LL)
#define ONBIT(n, i) (n (1 << (i)))
#define OFBIT(n, i) (n ^ (1 << (i)))
#define CNTBIT(n) __builtin_popcountll(n)
#define LOGG(n) (63 - __builtin_clzll(n))
#define MASK(i) (1LL << (i))
#define left(id) (id << 1LL)
#define right(id) ((id << 1LL) | (1LL))
#define mid(l, r) ((l + r ) >> 1ll)
template <class X, class Y> bool maximize(X &A, const Y &B){
if(A < B) return A = B, true;
return false;
}
template <class X, class Y> bool minimize(X &A, const Y &B){
if(A > B) return A = B, true;
return false;
}
const long long oo = 1e18;
const int INF = 1e9 + 1e8 + 1e7;
const int BLOCK = 320;
const int BASE = 311;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 100;
const int MAXVAL = 1e6 + 100;
int n, k;
vii G[MAXN];
bool del[MAXN];
int sz[MAXN], par[MAXN];
void dfs(int u, int pre){
sz[u] = 1;
FORV(v, G[u]){
if(v.fi == pre || del[v.fi]) continue;
dfs(v.fi, u);
sz[u] += sz[v.fi];
}
}
int findc(int u, int pre, int s){
FORV(v, G[u]){
if(v.fi == pre || del[v.fi]) continue;
if(sz[v.fi] > s / 2) return findc(v.fi, u, s);
}
return u;
}
ll ans = oo;
ll F[MAXN];
struct DATA{
int u, depth, dist;
};
vector <DATA> H;
void solve(int u, int pre, int d, int dist){
if(dist > k) return ;
minimize(ans, F[k - dist] + d);
H.pub({u, d, dist});
FORV(v, G[u]){
if(v.fi == pre || del[v.fi]) continue;
solve(v.fi, u, d + 1, dist + v.se);
}
}
void build(int u){
dfs(u, u);
int c = findc(u, u, sz[u]);
del[c] = 1;
set <int> sav;
FORV(tmp, G[c]){
int v = tmp.fi;
if(del[v]) continue;
solve(v, c, 1, tmp.se);
F[0] = 0;
FORV(x, H) {
if(x.dist <= k) minimize(F[x.dist], x.depth);
sav.insert(x.dist);
}
H.clear();
}
FORV(val, sav) F[val] = oo;
FORV(v, G[c]){
if(del[v.fi]) continue;
build(v.fi);
}
}
main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if(fopen(YAT ".inp", "r")) {
freopen(YAT ".inp","r",stdin);
freopen(YAT ".ans","w",stdout);
}
cin >> n >> k;
FOR(i, 1, n - 1){
int u, v, w;
cin >> u >> v >> w;
G[u].pub({v, w});
G[v].pub({u, w});
}
FOR(u, 0, k) F[u] = oo;
build(0);
if(ans >= oo / 2) ans = -1;
cout << ans ;
cerr << "PhcKhnhTapCode's TimeRun: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s. \n";
return (0 ^ 0);
}