이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5+5;
vector<pair<ll,ll>> adj[MAXN]; //first nodes, then weight
ll depth[MAXN],weightsum[MAXN],ans;
int n,k;
map<ll,ll> help[MAXN];
void dfs(int u, int p, ll d, int dep){
depth[u] = dep;
weightsum[u] = d;
help[u][d] = dep;
for(auto v : adj[u]){
if(v.first != p){
dfs(v.first,u,d+v.second,dep+1);
}
}
}
void smalltolarge(int u, int p){
ll tar = k+weightsum[u]*2;
for(auto v : adj[u]){
if(v.first != p){
smalltolarge(v.first,u);
if(help[v.first].size() > help[u].size()) swap(help[v.first],help[u]);
for(auto x : help[v.first]){
if(help[u].find(tar-x.first) != help[u].end()){
ans = min(ans,x.second+help[u][tar-x.first]-2*depth[u]);
}
}
for(auto x : help[v.first]){
if(help[u].find(x.first) == help[u].end()){
help[u].insert(x);
}
else{
help[u][x.first] = min(help[u][x.first],x.second);
}
}
}
}
}
int best_path(int N, int K, int edges[][2], int lengths[]){
if(K == 1) return 0;
n = N; k = K; ans = INT_MAX;
for(int i = 0;i<N-1;i++){
adj[edges[i][0]].push_back({edges[i][1],lengths[i]});
adj[edges[i][1]].push_back({edges[i][0],lengths[i]});
}
dfs(0,-1,0,0);
smalltolarge(0,-1);
return 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... |