| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 386958 | dongliu0426 | 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 "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int K = 1000010;
const int M = 2 * N;
const int inf = 0x3f3f3f3f;
int hd[N], nx[M], to[M], wt[M], ei = 0;
inline void link(int i, int j, int k) {
nx[++ei] = hd[i], wt[ei] = k, hd[i] = ei, to[ei] = j;
}
int n, k, ss[N], dep, cc[K], ans;
bool vv[N];
int subtree(int x, int p = 0) {
ss[x] = 1;
for (int j = hd[x], y; j; j = nx[j])
if (!vv[y = to[j]] && y != p)
ss[x] += subtree(y, x);
return ss[x];
}
int centroid(int dd, int x, int p = 0) {
for (int j = hd[x], y; j; j = nx[j])
if (!vv[y = to[j]] && y != p && ss[y] >= dd)
return centroid(dd, y, x);
return x;
}
void _fill(int x, int p, int w, int d) {
if (w > k) return;
cc[w] = min(cc[w], d);
dep = max(dep, d);
for (int j = hd[x], y; j; j = nx[j])
if (!vv[y = to[j]] && y != p)
_fill(y, x, w + wt[j], d + 1);
}
void _count(int x, int p, int w, int d) {
if (w > k) return;
ans = min(ans, d + cc[k - w]);
for (int j = hd[x], y; j; j = nx[j])
if (!vv[y = to[j]] && y != p)
_count(y, x, w + wt[j], d + 1);
}
void decomp(int x = 1) {
int c = centroid(subtree(x) / 2, x);
// do smth
dep = 0, vv[c] = 1;
for (int j = hd[c], y; j; j = nx[j])
if (!vv[y = to[j]])
_fill(y, c, wt[j], 1), _count(y, c, wt[j], 1);
for (int i = 1; i <= dep; ++i) cc[i] = inf;
for (int j = hd[c], y; j; j = nx[j])
if (!vv[y = to[j]])
decomp(y);
}
int best_path(int N, int K, int H[][2], int L[]){
n = N, k = K;
memset(vv, 0, sizeof(vv));
memset(hd, 0, sizeof(hd));
ans = inf, ei = 0;
for (int i = 1; i < n; ++i) {
link(H[i][0], H[i][1], L[i]);
link(H[i][1], H[i][0], L[i]);
}
memset(cc, 0x3f, sizeof(cc));
cc[0] = 0;
decomp();
return (ans == inf ? -1 : ans);
}