| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 882769 | dosts | 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;
#define sp << " " <<
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int lim = 2e5+1;
vector<pii> edges[lim];
vi d(lim),dd(lim,-1),dp(lim);
map<int,int> mp[lim];
void dep(int node,int p,int de = 0) {
d[node] = de;
dd[node] = dd[p]+1;
for (auto it : edges[node]) {
if (it.first != p) dep(it.first,node,de+it.second);
}
}
int k;
void dfs(int node,int p) {
mp[node][d[node]] = dd[node];
for (auto it : edges[node]) {
if (it.first == p) continue;
dp[node] = min(dp[node],dp[it.first]);
dfs(it.first,node);
if (mp[it.first].size() > mp[node].size()) mp[node].swap(mp[it.first]);
for (auto itt : mp[it.first]) {
if (mp[node].count(k+2*d[node]-itt.first)) {
dp[node] = min(dp[node],mp[node][k+2*d[node]-itt.first]+itt.second-2*dd[node]);
}
}
for (auto itt : mp[it.first]) {
if (!mp[node].count(itt.first)) mp[node].insert(itt);
else mp[node][itt.first] = min(mp[node][itt.first],itt.second);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
F(i,N-1) edges[H[i-1][0]+1].push_back({H[i-1][1]+1,L[i-1]});
dep(1,1);
dfs(1,1);
return dp[1];
}