이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 15;
vector<pair<int,int> > adj[MAXN];
map<long long,int> cost[MAXN];
int res = MAXN;
void dfs(int u,int p,long long k,long long d,int l){
cost[u][d] = l;
for(auto v : adj[u]){
if(v.first == p) continue;
dfs(v.first,u,k,d+v.second,l+1);
if(cost[u].size() < cost[v.first].size()) swap(cost[u],cost[v.first]);
for(auto w : cost[v.first]){
long long split = k - w.first + 2*d;
if(cost[v.first].count(split)) res = min(res,w.second+cost[v.first][split]-2*l);
if(cost[u].count(w.first)) cost[u][w.first] = min(cost[u][w.first],w.second);
else cost[u][w.first] = w.second;
}
}
if(cost[u].count(d+k)) res = min(res,cost[u][d+k]-l);
}
int best_path(int N, int K, int H[][2], int L[]){
for(int i=0;i<N-1;i++){
adj[H[i][0]].emplace_back(H[i][1],L[i]);
adj[H[i][1]].emplace_back(H[i][0],L[i]);
}
dfs(0,0,K,0,0);
if(res == MAXN) res = -1;
return res;
}
# | 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... |