이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
const static int INF = 1e9;
const int MAXN = 200001;
static int N, sumNeed;
static vector<pair<int, int>> adj[MAXN];
static int depth[MAXN], sum[MAXN];
static map<ll, ll> maps[MAXN];
static int ans = INF;
void dfs (int node = 0, int parent = -1) {
for (pair<int, int> nxt : adj[node]) {
int nodenxt = nxt.f, weightnxt = nxt.s;
if (nodenxt == parent) continue;
depth[nodenxt] = depth[node] + 1;
sum[nodenxt] = sum[node] + weightnxt;
dfs(nodenxt, node);
if (maps[nodenxt].size() > maps[node].size()) swap(maps[nodenxt], maps[node]);
for (pair<ll, ll> elem : maps[nodenxt]) {
int sumOn = elem.f, depthOn = elem.s;
int need = -sumOn + 2*sum[node] + sumNeed;
if (maps[node].find(need) != maps[node].end()) {
ans = min(ans, (int) (maps[node][need] - 2*depth[node] + depthOn));
}
if (maps[node].find(sumOn) == maps[node].end()) {
maps[node][sumOn] = depthOn;
}
else {
maps[node][sumOn] = min(maps[node][sumOn], (ll) depthOn);
}
}
maps[nodenxt].clear();
}
if (maps[node].find(sumNeed) != maps[node].end()) {
ans = min(ans, (int) (maps[node][sumNeed] - depth[node]));
}
}
int best_path(int N, int K, int H[][2], int L[])
{
::N = N;
sumNeed = K;
for (int i = 0; i < N-1; i++) {
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
dfs();
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... |