| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1139322 | Rufat | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
//Author RufatM
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<ld> vld;
typedef vector<vector<ld>> vvld;
typedef vector<ull> vull;
typedef vector<vector<ull>> vvull;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef vector<pii> vpii;
typedef vector<vector<pii>> vvp;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define eb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ff first
#define ss second
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pow(x, y) static_cast<int>(pow(x, y))
#define sz(x) (int)(x).sz()
#pragma GCC optimize("Ofast","unroll-loops","fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt")
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
template<typename T> inline T sqr(T x) {return x*x;}
template<typename T> inline T modinv(T a, T mod){return 0;}
template<class T> bool isPrime(T n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(T i=5;i*i<=n;i+=6)if(n%i==0||n%(i+2)==0)return false;return true;}
const int MOD = 1e9+7;
const int INF = 1e9 + 7;
const long long LINF = 1e18 + 7;
const int MAXN = 100005;
vector<vector<pair<int, ll>>> adj;
vector<map<ll, int>> dp;
ll dist;
int edges = INF;
ll K;
void dfs(int u, int p) {
dp[u][0] = 0;
for(auto &edge : adj[u]) {
int v = edge.first;
long long w = edge.second;
if(v==p) continue;
dfs(v,u);
for(auto &cv : dp[v]) {
long long distV = cv.first;
int edgesV = cv.second;
long long need = K - distV - w;
auto it = dp[u].find(need);
if(it != dp[u].end()) {
int totalEdges = it->second + edgesV + 1;
ansEdges = min(ansEdges, totalEdges);
}
}
for(auto &cv : dp[v]) {
long long distV = cv.first + w;
int edgesV = cv.second + 1;
if(dp[u].count(distV)==0) dp[u][distV] = edgesV;
else dp[u][distV] = min(dp[u][distV], edgesV);
}
}
int best_path(int N, long long Kinput, vector<vector<int>> &H, vector<long long> &L) {
K = Kinput;
adj.resize(N);
dp.resize(N);
for (int i = 0; i < N - 1; ++i) {
int u = H[i][0] - 1, v = H[i][1] - 1;
long long w = L[i];
adj[u].eb(v, w);
adj[v].eb(u, w);
}
dfs(0, -1);
return (edges == INF ? -1 : edges);
}
signed main() {
fastio;
int N;
long long Kinput;
cin >> N >> Kinput;
vector<vector<int>> H(N - 1, vector<int>(2));
vector<long long> L(N - 1);
for (int i = 0; i < N - 1; ++i) {
cin >> H[i][0] >> H[i][1] >> L[i];
}
cout << best_path(N, Kinput, H, L) << endl;
}