| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 849276 | manhtuan22007 | Race (IOI11_race) | C++14 | 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 name "race"
#define ll long long
//#define int long long
int n , k;
vector<vector<pair<int , int>>> g(200010);
namespace sub12{
const int maxn = 1e3 + 10;
int par[maxn][11] , h[maxn] , cost[maxn];
void dfs(int u){
for(auto e : g[u]){
int v = e.first;
if(v == par[u][0]) continue;
h[v] = h[u] + 1;
cost[v] = cost[u] + e.second;
par[v][0] = u;
for(int i = 1 ; i < 11 ; i ++){
par[v][i] = par[par[v][i - 1]][i - 1];
}
dfs(v);
}
}
int lca(int u , int v){
if(h[u] < h[v]) swap(u , v);
int k = h[u] - h[v];
for(int i = 0 ; (1 << i) <= k ; i ++){
if(k >> i & 1) u = par[u][i];
}
if(u == v) return u;
for(int i = 10 ; i >= 0 ; i --){
if(par[u][i] != par[v][i]){
u = par[u][i] , v = par[v][i];
}
}
return par[u][0];
}
void solve(){
dfs(1);
int res = -1;
for(int i = 1 ; i <= n ; i ++) for(int j = i + 1 ; j <= n ; j ++){
int p = lca(i , j);
int d = cost[i] + cost[j] - 2 * cost[p];
int num = h[i] + h[j] - 2 * h[p];
if(d == k) res = (res == -1 ? num : min(res , num));
}
cout << res << "\n";
}
}
namespace sub3{
const int maxn = 2e5 + 10;
int dp[maxn][205];
void dfs(int u , int p){
dp[u][0] = 0;
for(auto e : g[u]){
int v = e.first;
if(v == p) continue;
dfs(v , u);
for(int i = 0 ; i <= k ; i ++){
if(i + e.second <= k) dp[u][i + e.second] = min(dp[u][i + e.second] , dp[v][i] + 1);
}
}
}
void solve(){
memset(dp , 0x3f , sizeof dp);
int inf = dp[0][0];
dfs(1 , 0);
int res = -1;
for(int i = 1 ; i <= n ; i ++){
if(dp[i][k] == inf) continue;
res = (res == -1 ? dp[i][k] : min(res , dp[i][k]));
}
cout << res;
}
}
int32_t main()
{
if(fopen(name".inp" , "r")){
freopen(name".inp" , "r" , stdin);
freopen(name".out" , "w" , stdout);
}
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
for(int i = 1 ; i < n ; i ++){
int u , v , w;
cin >> u >> v >> w;
++u , ++v;
g[u].push_back({v , w});
g[v].push_back({u , w});
}
if(n <= 1000) sub12::solve();
else if(k <= 100) sub3::solve();
// sub3::solve();
}