| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1150878 | lidplf | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include "race.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb push_back
#define ll long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define MOD2 998244353
using namespace std;
int best_path(int n, int k, int H[][2], int L[])
{
vector<vector<pair<ll,ll>>> g(n);
for (int i = 0; i < n - 1; i++){
g[H[i][0]].emplace_back(make_pair(v,L[i]));
g[H[i][1]].emplace_back(make_pair(u,L[i]));
}
ll res = LLONG_MAX;
vector<map<ll,ll>> dist(n);
//dist(x) + dist(y) - 2*dist(z) = k
//k+2*dist(z) = dist(x) + dist(y)
//dist(y) = k+2*dist(z)-dist(x)
auto dfs = [&] (auto&& self, int node, int parent, int depth, ll p) -> void{
for (auto [neighbor, weight]: g[node]){
if (neighbor!=parent){
self(self,neighbor,node,depth+1,p+weight);
if (dist[neighbor].count(p+k)){
res = min(res, dist[neighbor][p+k] - depth);
}
if (dist[neighbor].size() > dist[node].size()) swap(dist[node], dist[neighbor]);
for (auto [pref, dep]: dist[neighbor]){
if (pref==p+k){
res = min(res, dep - depth);
}
else if (dist[node].count(k+2*p-pref)){
res = min(res, dist[node][k+2*p-pref] + dep - 2*depth);
}
if (!dist[node].count(pref)){
dist[node][pref] = dep;
}
else{
dist[node][pref] = min(dist[node][pref], dep);
}
}
}
}
dist[node][p] = depth;
};
dfs(dfs,0,0,0,0);
if (res==LLONG_MAX){
return -1;
}
else{
return res;
}
}