| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1118452 | alexdd | 경주 (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 "race.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
long long rez,K;
vector<pair<long long,long long>> con[200005];
map<long long,long long> dp[200005];
long long d[200005],d2[200005];
void dfs(int nod, int par)
{
if(d2[nod]==K) rez = min(rez, d[nod]);
long long maxc=-1,heavy=-1;
for(auto [adj,w]:con[nod])
{
if(adj==par)
continue;
d[adj] = d[nod] + 1;
d2[adj] = d2[nod] + w;
dfs(adj,nod);
if((int)dp[adj].size() > maxc)
maxc = dp[adj].size(), heavy=adj;
}
if(heavy==-1)
{
}
else
{
swap(dp[nod], dp[adj]);
for(auto [adj,w]:con[nod])
{
if(adj==par || adj==heavy)
continue;
for(auto it:dp[adj])
{
rez = min(rez, it.second + dp[nod][K-it.first] + 2LL*INF - 2LL*d[nod]);
}
for(auto it:dp[adj])
dp[nod][it.first] = min(dp[nod][it.first], it.second);
}
}
dp[d2[nod]] = min(dp[d2[nod]], d[nod] - INF);
}
int best_path(int N, int copK, int H[][2], int L[])
{
K = copK;
rez = N+2;
for(int i=0;i<N-1;i++)
{
con[H[i][0]].push_back({H[i][1],L[i]});
con[H[i][1]].push_back({H[i][0],L[i]});
}
dfs(0,-1);
if(rez==N+2)
rez=-1;
return rez;
}