| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 539379 | noedit | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
#define int long long
const int MAXN = 2e5;
const int MAXK = 1e6 + 1;
vector<pair<int, int> > g[MAXN];
vector<int>* vec[MAXN];
int sz[MAXN], big[MAXN];
map<int, int> cnt[MAXK];
int dep[MAXN], d[MAXN];
void sizes(int v, int p, int depth = 0, int dist = 0)
{
dep[v] = depth;
d[v] = dist;
sz[v] = 1;
int b = -1, mx = 0;
for (auto& [u, w]: g[v])
{
if (u != p)
{
sizes(u, v, depth + 1, dist + w);
sz[v] += sz[u];
if (sz[u] > mx)
{
mx = sz[u];
b = u;
}
}
}
big[v] = b;
}
int ans = 1e9, k, n;
void dfs(int v, int p, bool keep = 0)
{
for (auto& [u, w] : g[v])
{
if (u != p && u != big[v])
{
dfs(u, v, 0);
}
}
if (big[v] != -1)
{
dfs(big[v], v, 1);
vec[v] = vec[big[v]];
}
else
{
vec[v] = new vector<int>();
}
vec[v]->push_back(v);
int y = k + d[v];
if (cnt[y].size() > 0 && cnt[y].begin()->first - dep[v] < ans)
{
ans = cnt[y].begin()->first - dep[v];
}
if (d[v] < MAXK)
{
cnt[d[v]][dep[v]]++;
}
for (auto& [u, w] : g[v])
{
if (u != p && u != big[v])
{
for (auto& w : *vec[u])
{
int x = k + 2 * d[v] - d[w];
if (x >= 0 && x < MAXK && cnt[x].size() > 0)
{
int cur = cnt[x].begin()->first + dep[w];
if (cur - 2 * dep[v] < ans)
{
ans = cur - 2 * dep[v];
}
}
vec[v]->push_back(w);
}
for (auto& w : *vec[u])
if (d[w] < MAXK)
cnt[d[w]][dep[w]]++;
}
}
if (!keep)
{
for (auto& u : *vec[v])
{
if (d[u] < MAXK){
cnt[d[u]][dep[u]]--;
if (!cnt[d[u]].count(dep[u]))
cnt[d[u]].erase(dep[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++)
{
int x = H[i][0], y = H[i][1], z = L[i];
g[x].push_back({y, z});
g[y].push_back({x, z});
}
sizes(0, 0);
dfs(0, 0);
return (ans == 1e9 ? -1 :ans);
}
/*
4 3
0 1 1
1 2 2
1 3 4
2
*/