| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 386958 | dongliu0426 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}