이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
void fastIO(){
ios_base::sync_with_stdio(false);
cin.tie(0);
}
vector<pair<int, int> > edges[200100];
int sub[200100];
bool rem[200100];
int LEN;
void dfs(int node, int pa = 0){
sub[node] = 1;
for (pair<int, int> nx : edges[node]){
if (nx.first == pa || rem[nx.first])
continue;
dfs(nx.first, node);
sub[node] += sub[nx.first];
}
}
int centroid(int node, int sz, int pa = 0){
for (pair<int, int> nx : edges[node]){
if (nx.first == pa || rem[nx.first])
continue;
if (sub[nx.first] > sz/2)
return centroid(nx.first, sz, node);
}
return node;
}
void dfs2(int node, int dep, int cur, map<int, int> &mp, int pa = 0){
if (mp.count(dep))
mp[dep] = min(mp[dep], cur);
else
mp[dep] = cur;
for (pair<int, int> nx : edges[node]){
if (nx.first == pa || rem[nx.first])
continue;
dfs2(nx.first, dep+nx.second, cur+1, mp, node);
}
}
int decomp(int node){
dfs(node);
int cent = centroid(node, sub[node]);
rem[cent] = true;
map<int, int> mp;
int curmin = 999999999;
mp[0] = 0;
for (pair<int, int> nx : edges[cent]){
if (rem[nx.first])
continue;
map<int, int> tmp;
dfs2(nx.first, nx.second, 1, tmp);
for (auto it = tmp.begin(); it != tmp.end(); it++){
if (mp.count(LEN-(*it).first))
curmin = min(curmin, (*it).second+mp[LEN-(*it).first]);
}
for (auto it = tmp.begin(); it != tmp.end(); it++){
if (!mp.count((*it).first))
mp[(*it).first] = (*it).second;
else
mp[(*it).first] = min(mp[(*it).first], mp[(*it).second]);
}
}
int totmin = curmin;
for (pair<int, int> nx : edges[cent]){
if (rem[nx.first])
continue;
totmin = min(totmin, decomp(nx.first));
}
return totmin;
}
int best_path(int N, int K, int H[][2], int *L){
LEN = K;
for (int i = 0; i < N-1; i++){
int a = H[i][0], b = H[i][1];
a++, b++;
edges[a].push_back({b, L[i]});
edges[b].push_back({a, L[i]});
}
return decomp(1);
}
# | 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... |