| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 650749 | DeMen100ns | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const long long INF = 1e18 + 7;
const int MAXA = 1e9;
const int B = sqrt(N) + 5;
vector <pair<int, int>> a[N];
int h[N], e[N], n, k;
int ans = MAXA;
map <int, int> m[N];
void dfs(int u, int par = -1){
for(pair<int, int> st : a[u]){
int i = st.first, w = st.second;
if (i == par) continue;
e[i] = e[u] + 1;
h[i] = h[u] + w;
dfs(i, u);
if (m[u].empty()){
swap(m[u], m[i]);
if (m[u].find(k + h[u]) != m[u].end()) ans = min(ans, m[u][k + h[u]] - e[u]);
if (m[u].find(h[u]) != m[u].end()) m[u][h[u]] = min(m[u][h[u]], e[u]);
else m[u][h[u]] = e[u];
} else {
for(pair<int, int> st : m[i]){
int h1 = st.first, e1 = st.second;
//h1 + x - 2 * h[u] = k
if (m[u].find(k - h1 + 2 * h[u]) != m[u].end()){
ans = min(ans, e1 + m[u][k - h1 + 2 * h[u]] - 2 * e[u]);
}
}
for(pair<int, int> st : m[i]){
int h1 = st.first, e1 = st.second;
if (m[u].find(h1) != m[u].end()){
m[u][h1] = min(m[u][h1], e1);
} else m[u][h1] = e1;
}
}
}
if (m[u].empty()) m[u][h[u]] = e[u];
}
int best_path(int N, int K, int H[][2], int L[]){
n = N; k = K;
for(int i = 0; i < N - 1; ++i){
a[H[i][0]].push_back({H[i][1], L[i]});
a[H[i][1]].push_back({H[i][0], L[i]});
}
for(int i = 0; i < N; ++i){
sort(a[i].begin(), a[i].end(), [](pair<int, int> v1, pair<int, int> v2){return a[v1.first].size() > a[v2.first].size();});
}
dfs(0);
if (ans == MAXA) return -1;
else return ans;
}