이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
const int mxN = 2e5+5;
using pii = pair<int,int>;
vector<pii> tr[mxN];
int N, K, res = LLONG_MAX, tin[mxN],tout[mxN], jump[mxN][19], lr[mxN], dr[mxN], dep, di, timer;
bool anc(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }
void dfs(int x, int p) {
dep++;
lr[x] = dep, dr[x] = di, tin[x] = ++timer, jump[x][0] = p;
for(int i = 1; i <= 18; i++) jump[x][i] = jump[jump[x][i-1]][i-1];
for(auto it : tr[x]) if(it.second != p) {
di += it.first;
dfs(it.second,x);
di -= it.first;
}
dep--, tout[x] = ++timer;
}
int lca(int u, int v) {
if(anc(u,v))return u;
if(anc(v,u))return v;
for(int i = 18; i >= 0; i--) if(!anc(jump[u][i],v)) u = jump[u][i];
return jump[u][0];
}
int len(int u, int v) {
return lr[u]+lr[v]-2*lr[lca(u,v)];
}
int dist(int u, int v) { return dr[u]+dr[v]-2*dr[lca(u,v)]; }
signed best_path(signed n, signed k, signed h[][2], signed l[]) {
N = n, K = k;
for(int i = 0; i < N-1; i++) {
int a = h[i][0], b = h[i][1], w = l[i];
tr[a].push_back({w,b});
tr[b].push_back({w,a});
}
dfs(0,0);
int res = LLONG_MAX;
for(int i = 0; i < N; i++) {
for(int j = i+1; j < N; j++) {
if(dist(i,j) == K) res = min(res, len(i,j));
}
}
if(res == LLONG_MAX) return -1; else 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... |