| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1164321 | sdkiungdhydnsajkrmwqiedjn | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define task "file"
#define fi first
#define pb push_back
#define eb emplace_back
#define se second
typedef long long ll;
using pii = pair<int, int>;
#define int ll
const int nmax = 2e5 + 5, inf = 1e9;
int n, k, h[nmax][2], l[nmax];
int vis[nmax], sz[nmax];
vector<pii> adj[nmax];
unordered_map<int, int> mpa, mp;
int size(int u, int p = -1)
{
sz[u] = 1;
for (auto [v, w] : adj[u])
{
if (v != p && !vis[v])
{
sz[u] += size(v, u);
}
}
return sz[u];
}
int find(int u, int n, int p = -1)
{
for (auto [v, w] : adj[u])
{
if (v != p && !vis[v] && sz[v] > n / 2)
{
return find(v, n, u);
}
}
return u;
}
void cal(int u, int depth, int k, int cnt, int p = -1)
{
if (depth > k)
{
return;
}
if (mp.count(depth) == 0)
mp[depth] = cnt;
else
mp[depth] = min(mp[depth], cnt);
for (auto [v, w] : adj[u])
{
if (vis[v] || v == p)
{
continue;
}
cal(v, depth + w, k, cnt + 1, u);
}
}
int ans = inf;
void dfs_cal(int u, int k)
{
int cent = find(u, size(u));
if (vis[cent])
return;
vis[cent] = true;
mpa[0] = 0;
for (auto [v, w] : adj[cent])
{
if (vis[v])
continue;
cal(v, w, k, 1);
for (auto x : mp)
{
if (k - x.fi < 0 || mpa.count(k - x.fi) == 0)
continue;
ans = min(ans, x.se + mpa[k - x.fi]);
}
for (auto x : mp)
{
if (mpa.count(x.fi) == 0)
mpa[x.fi] = x.se;
else
mpa[x.fi] = min(mpa[x.fi], x.se);
}
mp.clear();
}
mpa.clear();
for (auto [v, w] : adj[cent])
{
if (!vis[v])
{
dfs_cal(v, k);
}
}
}
int best_path(int n, int k, int h[][2], int l[])
{
memset(vis, 0, sizeof(vis));
for (int i = 0; i < n - 1; i++) {
h[i][0] ++, h[i][1] ++;
adj[h[i][0]].emplace_back(h[i][1], l[i]);
adj[h[i][1]].emplace_back(h[i][0], l[i]);
}
dfs_cal(1, k);
if (ans == inf)
return -1;
return ans;
}