| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 639984 | SuchPigeon | 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>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;
typedef ld COMPTYPE;
//typedef complex<COMPTYPE> point;
#define IOS cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
#define FILEIOS(fn) freopen(fn".in", "r", stdin); freopen(fn".out", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510
#define xx real()
#define yy imag()
#define ff first
#define ss second
#define nl "\n"
#define bl " "
#define pb push_back
template<typename T>
bool chmax(T& val, T nval) { if(val < nval) {val=nval; return true;} return false;}
template<typename T>
bool chmin(T& val, T nval) { if(val > nval) {val=nval; return true;} return false;}
void DEBUGOUT() { cerr << '\n'; }
template<typename Head, typename... Tail>
void DEBUGOUT(Head H, Tail... T) { cerr << ' ' << H; DEBUGOUT(T...); }
#define DEBUG(...) cerr << "(" << #__VA_ARGS__ << "):"; DEBUGOUT(__VA_ARGS__)
void WRITEIN() { return; }
template<typename Head, typename... Tail>
void WRITEIN(Head& H, Tail&... T) { cin >> H; WRITEIN(T...); }
#define win(...) WRITEIN(__VA_ARGS__);
void WRITEOUT() { return; }
template<typename Head, typename... Tail>
void WRITEOUT(Head&& H, Tail&&... T) { cout << H; WRITEOUT(T...); }
#define wout(...) WRITEOUT(__VA_ARGS__);
const int N = 2e5+1;
const int INF = N*2;
int sz[N];
vector<pli> g[N];
vector<pli> vec[N];
int ans=INF;
int n;
ll k;
void dfs_sz(int v, int p) {
sz[v] = 1;
for(auto& [c,u] : g[v]) {
if(p == u) continue;
dfs_sz(u,v);
sz[v] += sz[u];
}
}
void dfs_hld(int v, int p, int keep) {
int nextu=-1,maxsz=-1;
ll nextc;
for(auto& [c,u] : g[v]) {
if(u == p) continue;
if(maxsz < sz[u]) {
maxsz = sz[u];
nextu = u;
nextc = c;
}
}
for(auto& [c,u] : g[v]) {
if(u == p || u == nextu) continue;
dfs_hld(u,v,0);
}
if(nextu != -1) {
dfs_hld(nextu,v,1);
swap(vec[nextu], vec[v]);
for(auto& [c,sz] : vec[v]) {
sz++;
c += nextc;
if(c==k) chmin(ans,sz);
}
}
for(auto& [c,u] : g[v]) {
if(u == p || u == nextu) continue;
for(auto& [cc,sz] : vec[u]) {
if(cc+c > k || sz+1 >= ans) continue;
vec[v].pb({cc+c,sz+1});
if(cc+nextc==k) chmin(ans,sz+1);
}
}
vec[v].pb({0ll,0});
/*
DEBUG(v);
for(auto& [c,sz] : g[v]) {
DEBUG(c,sz);
}
*/
}
int32_t main() {
IOS;
int v,u;
ll c;
win(n,k);
for(int i = 1; i < n; i++) {
win(v,u,c);
g[v].pb({c,u});
g[u].pb({c,v});
}
dfs_sz(0,0);
dfs_hld(0,0,1);
if(ans == INF) ans=-1;
wout(ans,nl);
}