| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 886936 | fryingduc | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int maxn = 1e6+5;
const int inf = 1e18+10;
int n, l;
int sz[maxn], tin[maxn], tout[maxn], timer, h[maxn];
int dak[maxn], depth[maxn], et[maxn];
vector<pair<int, int>> g[maxn];
multiset<int> mn[maxn];
vector<int> vec;
int ans = inf;
void pre_dfs(int u, int prev){
sz[u] = 1;
tin[u] = ++timer;
et[timer] = u;
for(auto e:g[u]){
int v = e.first, w = e.second;
if(v == prev) continue;
depth[v] = depth[u] + 1;
h[v] = h[u] + w;
pre_dfs(v, u);
sz[u] += sz[v];
}
tout[u] = timer;
}
void dfs(int u, int prev, bool keep){
int bigchild = -1;
for(auto e:g[u]){
int v = e.first;
if(v == prev) continue;
if(bigchild == -1 || sz[bigchild] < sz[v]) bigchild = v;
}
for(auto e:g[u]){
int v = e.first;
if(v == prev || v == bigchild) continue;
dfs(v, u, 0);
}
if(bigchild != -1) dfs(bigchild, u, 1);
int mim = lower_bound(vec.begin(), vec.end(), h[u] + l) - vec.begin();
if(mim < vec.size() and vec[mim] == h[u] + l){
if(mn[mim].size()) ans = min(ans, *mn[mim].begin() - depth[u]);
}
mn[dak[u]].insert(depth[u]);
for(auto e:g[u]){
int v = e.first;
if(v == prev || v == bigchild) continue;
for(int i = tin[v]; i <= tout[v]; ++i){
int val = 2 * h[u] + l - h[et[i]];
int pos = lower_bound(vec.begin(), vec.end(), val) - vec.begin();
if(pos < (int)vec.size() and vec[pos] == val){
if(mn[pos].size()) ans = min(ans, *mn[pos].begin() + depth[et[i]] - 2 * depth[u]);
}
}
for(int i = tin[v]; i <= tout[v]; ++i){
mn[dak[et[i]]].insert(depth[et[i]]);
}
}
if(keep) return;
for(int i = tin[u]; i <= tout[u]; ++i){
mn[dak[et[i]]].erase(depth[et[i]]);
}
}
int best_path(int n, int k, int edges[][2], int weights[]){
cin >> n >> l;
for(int i = 0; i < n - 1; ++i){
int u = edges[i][0], v = edges[i][1], w = weights[i];
++u, ++v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
pre_dfs(1, 0);
for(int i = 1; i <= n; ++i){
vec.push_back(h[i]);
}
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
for(int i = 1; i <= n; ++i){
dak[i] = lower_bound(vec.begin(), vec.end(), h[i]) - vec.begin();
}
dfs(1, 0, 1);
return (ans > n ? -1 : ans);
}