| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 900168 | subrat0018 | 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;
#define ll long long
#define nline "\n"
using uint = unsigned int;
using ull = unsigned long long;
const ll M = 1e9 + 7;
const ll M2 = 998244353;
const ll INF = 2e18;
const ll N = 1e6 + 10;
const double Degree = 57.2958;
/***************************************Debug***********************************************************/
/***************************************Debug***********************************************************/
/***************************************Debug***********************************************************/
#ifndef ONLINE_JUDGE
#define debug(x) cerr<< #x << " ";_print(x);cerr<<nline;
#else
#define debug(x)
#endif
void _print(int x) {cerr << x;}
void _print(bool x) {cerr << x;}
void _print(char x) {cerr << x;}
void _print(string x) {cerr << x;}
void _print(ll x) {cerr << x;}
void _print(ull x) {cerr << x;}
void _print(float x) {cerr << x;}
void _print(double x) {cerr << x;}
template<class T>void _print(set<T> v);
template<class T>void _print(vector<T> v);
template<class T>void _print(multiset<T> v);
template<class T>void _print(unordered_set<T> v);
template<class T, class V>void _print(map<T, V> v);
template<class T, class V>void _print(unordered_map<T, V> v);
template<class T>void _print(vector<vector<T>> v);
template<class T>void _print(stack<T> v);
template<class T>void _print(queue<T> v);
template<class T, class V>void _print(pair<T, V> p);
template<class T>void _print(queue<T> v) {cerr << "[ "; while (!v.empty()) {_print(v.front()); cerr << " "; v.pop();} cerr << " ]";}
template<class T>void _print(stack<T> v) {cerr << "[ "; while (!v.empty()) {_print(v.top()); cerr << " "; v.pop();} cerr << " ]";}
template<class T, class V>void _print(pair<T, V> p) {_print(p.first); cerr << " "; _print(p.second); cerr << nline;}
template<class T>void _print(set<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(vector<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(multiset<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T>void _print(unordered_set<T> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << " ";} cerr << "]";}
template<class T, class V>void _print(map<T, V> v) {cerr << "[ "; for (auto &i : v) {_print(i.first); cerr << " "; _print(i.second); cerr << "\n";} cerr << "]";}
template<class T, class V>void _print(unordered_map<T, V> v) {cerr << "[ "; for (auto &i : v) {_print(i.first); cerr << " "; _print(i.second); cerr << "\n";} cerr << "]";}
template<class T>void _print(vector<vector<T>> v) {cerr << "[ "; for (auto &i : v) {_print(i); cerr << nline;} cerr << "]";}
/************************************************************************************************************/
/************************************************************************************************************/
/************************************************************************************************************/
ll n,k;
ll sz[N];
bool dead[N];
ll dist[N];
vector<pair<ll, ll>> g[N];
vector<ll> temp;
void prep(int v,ll d, ll len, int par = -1)
{
if(len > k)return;
dist[len] = min(dist[len], d);
temp.push_back(len);
for(auto &val:g[v])
{
if(val.first == par || dead[val.first])continue;
prep(val.first, d + 1, len + val.second, v);
}
}
ll func(int v, ll d, ll len, int par = -1)
{
if(len > k)return INF;
ll ans = d + dist[k - len];
debug(v);
debug(d);
debug(dist[k - len]);
for(auto &val:g[v])
{
if(val.first == par || dead[val.first])continue;
ans = min(ans, func(val.first, d + 1, len + val.second, v));
}
return ans;
}
void dfs(int v, int par=-1)
{
sz[v] = 1;
for(auto &val:g[v])
{
if(val.first != par && !dead[val.first])
{
dfs(val.first, v);
sz[v] += sz[val.first];
}
}
}
int find_centroid(int currSize, int v, int par = -1)
{
for(auto &val:g[v])
if(val.first != par && !dead[val.first] && 2 * sz[val.first] > currSize)
return find_centroid(currSize, val.first, v);
return v;
}
ll decompose(int v)
{
dfs(v);
int centorid = find_centroid(sz[v], v);
dead[centorid] = true;
ll ans = INF;
temp.clear();
dist[0] = 0;
for(auto &val:g[centorid])
{
if(!dead[val.first])
{
ans = min(func(val.first, 1, val.second, centorid), ans);
prep(val.first, 1, val.second, centorid);
}
}
dist[0] = INF;
for(auto &val:temp)
dist[val] = INF;
for(auto &val:g[centorid])
if(!dead[val.first])
ans = min(ans, decompose(val.first));
return ans;
}
void best_path(int, int, int (*) [2], int*)
{
ll ans = decompose(0);
if(ans >= INF)
cout<<-1<<nline;
else
cout<<ans<<nline;
}
void solve()
{
cin>>n>>k;
vector<pair<ll, ll>> arr;
for(int i=0;i<N;i++)
dist[i] = INF;
for(int i=0;i<n-1;i++)
{
ll u,v;
cin>>u>>v;
arr.push_back({u,v});
}
for(auto &val:arr)
{
ll w;
cin>>w;
g[val.first].push_back({val.second, w});
g[val.second].push_back({val.first, w});
}
int x[n-1][2];
int y[n-1];
best_path(n,k,x,y);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("debug.txt", "w", stderr);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin>>t;
// prec();
for (int i = 1; i <= t; i++)
{
// cout<<"Case "<<i<<": ";
solve();
}
return 0;
}