| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 886246 | AgentPengin | 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: AgentPengin ( Độc cô cầu bại )
* created: 23.12.2022 10:08:02
* too lazy to update time
**/
#include<bits/stdc++.h>
#define EL '\n'
#define fi first
#define se second
#define NAME "TASK"
#define ll long long
#define lcm(a,b) (a/gcd(a,b))*b
#define db(val) "["#val" = " << (val) << "] "
#define bend(v) (v).begin(),(v).end()
#define sz(v) (int)(v).size()
#define ex exit(0)
#define int ll
using namespace std;
const ll mod = 1e9 + 7;
const int inf = 0x1FFFFFFF;
const int MAXN = 2e5 + 5;
int n,k,sz[MAXN],ans = inf;
vector<pair<int,int>> adj[MAXN];
bool deleted[MAXN];
int get_subtree_sizes(int u,int p = 0) {
sz[u] = 1;
for (auto v : adj[u]) {
if (!deleted[v.fi] && v.fi != p) {
sz[u] += get_subtree_sizes(v.fi,u);
}
}
return sz[u];
}
int find_centroid(int desired,int u,int p = 0) {
for (auto v : adj[u]) {
if (v.fi != p && !deleted[v.fi] && sz[v.fi] >= desired) {
return find_centroid(desired,v.fi,u);
}
}
return u;
}
unordered_map<int,int> mp;
vector<pair<int,int>> update;
void dfs(int u,int p,int len,int depth) {
if (len > k) return;
if (mp.count(k - len)) {
ans = min(ans,mp[k - len] + depth);
}
update.emplace_back(len,depth);
for (auto v : adj[u]) {
if (v.fi != p && !deleted[v.fi]) {
dfs(v.fi,u,len + v.se,depth + 1);
}
}
}
void solve(int u) {
int centroid = find_centroid(get_subtree_sizes(u) >> 1,u);
mp[0] = 0;
for (auto v : adj[centroid]) {
if (deleted[v.fi]) continue;
// solve for v
dfs(v.fi,centroid,v.se,1);
for (auto x : update) {
if (!mp.count(x.fi)) mp[x.fi] = x.se;
else mp[x.fi] = min(mp[x.fi],x.se);
}
// update for v
}
mp.clear();
deleted[centroid] = true;
for (auto v : adj[centroid]) {
if (!deleted[v.fi]) {
solve(v.fi);
}
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
if (ifstream(NAME".inp")) {
freopen(NAME".inp","r",stdin);
freopen(NAME".out","w",stdout);
}
cin >> n >> k;
for (int i = 1;i < n;i++) {
int u,v,l;
cin >> u >> v >> l;
u++,v++;
adj[u].emplace_back(v,l);
adj[v].emplace_back(u,l);
}
solve(1);
if (ans > n) cout << -1;
else cout << ans;
cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
return 0;
}
// agent pengin wants to take apio (with anya-san)