| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1068228 | apper | 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>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
/*------------------------------------code------------------------------------*/
const ll MAXN=1e5+9;
const ll INF=1e9+9;
const ll R=(1<<18);
const int X=18;
//const ll M=1e9+7;
//const ll P=47;
int n, k;
vector<pair<int, int>> adj[MAXN];
vector<pair<int, int>> edges;
int ans=INF;
void dfs(int v, int p, ll d, int cnt)
{
if(d==k)
{
ans=min(ans, cnt);
return;
}
for(auto [u, w] : adj[v])
{
if(u==p || d+w>k || cnt+1>ans)
continue;
dfs(u, v, d+w, cnt+1);
}
}
void solve()
{
for(int i=1;i<=n;i++)
dfs(i, -1, 0, 0);
cout<<(ans==INF ? -1 : ans);
}
int main()
{
cin.tie(0); ios_base::sync_with_stdio(0);
cin>>n>>k;
for(int i=0,a,b;i<n-1;i++)
{
cin>>a>>b;
edges.pb(make_pair(a, b));
}
for(int i=0,w;i<n-1;i++)
{
cin>>w;
auto [a, b] = edges[i];
adj[a].pb({b, w});
adj[b].pb({a, w});
}
edges.clear();
solve();
return 0;
}