이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
map<long long, int> mp;
int sz[maxn];
int dep1[maxn];
long long dep2[maxn];
vector<pair<int, int>> g[maxn];
void add(long long val, int dep){
if(mp.find(val) != mp.end())mp[val] = min(mp[val], dep);
else mp[val] = dep;
}
int query(long long val){
if(mp.find(val) == mp.end())return maxn;
else return mp[val];
}
// k = dep[a] + dep[b] - 2*dep[lca] => dep[b] = k - dep[a] + 2*dep[lca];
void pre_dfs(int x, int p){
sz[x] = 1;
for(auto v: g[x]){
if(v.first == p)continue;
dep1[v.first] = dep1[x] + 1;
dep2[v.first] = dep2[x] + v.second;
pre_dfs(v.first, x);
}
}
int dfs_query(int x, int p, long long coeff){
int re = query(coeff - dep2[x]) + dep1[x];
for(auto v: g[x]){
if(v.first == p)continue;
re = min(re, dfs_query(v.first, x, coeff));
}
return re;
}
void dfs_add(int x, int p){
add(dep2[x], dep1[x]);
for(auto v: g[x]){
if(v.first == p)continue;
dfs_add(v.first, x);
}
}
int dfs(int x, int p, int k){
sz[x] = 1;
int ans = maxn, bg = -1;
for(auto v: g[x]){
if(v.first == p)continue;
if(bg == -1 || sz[bg] < sz[v.first])bg = v.first;
}
for(auto v: g[x]){
if(v.first == p || v.first == bg)continue;
ans = min(ans, dfs(v.first, x, k));
mp.clear();
}
if(bg != -1)dfs(bg, x, k);
for(auto v: g[x]){
if(v.first == p || v.first == bg)continue;
ans = min(ans, dfs_query(v.first, x, 2*dep2[x] + k) - 2*dep1[x]);
dfs_add(v.first, x);
}
ans = min(ans, query(dep2[x] + k) - dep1[x]);
add(dep2[x], dep1[x]);
return ans;
}
int best_path(int N, int K, int H[][2], int L[])
{
dep1[0] = 0;
dep2[0] = 0;
for(int i = 0; i < N; i++)g[i].clear();
for(int i = 0; i < N-1; i++){
g[H[i][0]].push_back({H[i][1], L[i]});
g[H[i][1]].push_back({H[i][0], L[i]});
}
pre_dfs(0, -1);
int ans = dfs(0, -1, K);
return ans == maxn ? -1 : ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |