#include "race.h"
#include<bits/stdc++.h>
using namespace::std;
struct CentroidDecomposition {
int n;
int L;
int T;
vector<int> a;
vector<int> h;
vector<int> in;
vector<int> sz;
vector<int> out;
vector<int> best;
vector<int> depth;
vector<bool> removed;
vector<vector<pair<int, int>>> G;
CentroidDecomposition(int n, int k) :
n(n),
L(k),
a(n),
h(n),
in(n),
sz(n),
out(n),
best(k + 1, -1),
depth(n),
removed(n, false),
G(n)
{}
void add_edge(int u, int v, int w) {
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
void DFS(int u, int p = -1) {
sz[u] = 1;
for(auto e : G[u]) {
if(e.first == p or removed[e.first]) continue;
DFS(e.first, u);
sz[u] += sz[e.first];
}
}
int centroid(int u, int p, int n) {
for(auto e : G[u]) {
if(e.first == p or removed[e.first]) continue;
if(2 * sz[e.first] > n) return centroid(e.first, u, n);
}
return u;
}
void set_info(int u, int p = -1) {
a[T] = u;
in[u] = T++;
for(auto e : G[u]) {
int v, w;
tie(v, w) = e;
if(v == p or removed[v]) continue;
depth[v] = depth[u] + 1;
h[v] = h[u] + w;
set_info(v, u);
}
out[u] = T - 1;
}
int compute(int u) {
h[u] = depth[u] = T = 0;
set_info(u);
int res = -1;
best[0] = 0;
cout << "Root = " << u << endl;
for(auto e : G[u]) {
if(removed[e.first]) continue;
int v, w;
tie(v, w) = e;
cout << "Subtree = " << v << endl;
for(int i = in[v]; i <= out[v]; i++) {
int x = a[i];
if(h[x] > L) continue;
cout << "Node " << x << " --> " << h[x] << endl;
cout << "Want = " << L - h[x] << ". Best = " << best[L - h[x]] << endl;
if(~best[L - h[x]]) {
cout << "Here" << endl;
int cand = best[L - h[x]] + depth[x];
if(res == -1 or cand < res) res = cand;
}
}
cout << endl;
for(int i = in[v]; i <= out[v]; i++) {
int x = a[i];
if(h[x] > L) continue;
if(best[h[x]] == -1 or best[h[x]] > depth[x]) best[h[x]] = depth[x];
}
}
for(int i = in[u]; i <= out[u]; i++) {
int x = a[i];
if(h[x] > L) continue;
best[h[x]] = -1;
}
cout << "Final answer for node " << u << " --> " << res << endl;
return res;
}
int decompose(int rt, int p = -1) {
DFS(rt, p);
int c = centroid(rt, p, sz[rt]);
cout << "Centroid is: " << c << endl;
int res = compute(c);
removed[c] = true;
cout << "New removed table: " << endl;
for(int i = 0; i < n; i++) {
cout << removed[i] << " ";
}
cout << endl;
for(auto e : G[c]) {
if(removed[e.first]) continue;
int cur = decompose(e.first, c);
if(cur == -1) continue;
if(res == -1 or res > cur) res = cur;
}
return res;
}
int solve() {
return decompose(0);
}
};
int best_path(int N, int K, int H[][2], int L[]) {
CentroidDecomposition Solver(N, K);
for(int i = 0; i < N - 1; i++) {
Solver.add_edge(H[i][0], H[i][1], L[i]);
}
return Solver.solve();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
