| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 957842 | MisterReaper | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <race.h>
using i64 = long long;
constexpr int maxN = 2E5 + 5;
int n, k;
std::map<i64, int> s[maxN];
std::vector<std::pair<int, int>> adj[maxN];
int h[maxN], d[maxN];
int ans = maxN;
void dfs(int node, int par) {
for(auto [child, w] : adj[node]) {
if(child == par) {
continue;
}
h[child] = h[node] + w;
d[child] = d[node] + 1;
dfs(child, node);
}
return;
}
void s2l(int node, int par) {
i64 target = k + h[node] * 2;
s[node][h[node]] = d[node];
for(auto [child, w] : adj[node]) {
if(child == par) {
continue;
}
s2l(child, node);
if(s[child].size() > s[node].size()) {
std::swap(s[child], s[node]);
}
for(auto [a, b] : s[child]) {
if(s[node].count(target - a)) {
ans = std::min(ans, s[node][target - a] + b - 2 * d[node]);
}
}
for(auto [a, b] : s[child]) {
if(!s[node].count(a)) {
s[node][a] = n;
}
s[node][a] = std::min(s[node][a], b);
}
}
/*
std::cerr << "node: " << node << "\n";
for(auto [a, b] : s[node]) {
std::cerr << a << " " << b << "\n";
}
*/
}
int bestpath(int N, int K, int H[][2], int L[]) {
n = N;
k = K;
for(int i = 0; i < n - 1; i++) {
//std::cerr << H[i][0] << " " << H[i][1] << " :: " << L[i] << "\n";
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
dfs(0, -1);
s2l(0, -1);
if(ans == maxN) {
ans = -1;
}
return ans;
}