// time-limit: 3000
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
void setIO(string File_name) {
cin.tie(0)->sync_with_stdio(0);
if (File_name.size()) {
freopen((File_name + ".in").c_str(), "r", stdin);
freopen((File_name + ".out").c_str(), "w", stdout);
}
}
class CD {
private:
vector<vector<pair<int, long long>>> tree;
vector<int> par;
vector<int> sub;
vector<bool> rem;
map<long long, int> mp;
int ans = -1;
int k;
int dfs(int u, int p) {
sub[u] = 1;
for (auto [v, w] : tree[u]) {
if (!rem[v] && v != p) {
sub[u] += dfs(v, u);
}
}
return sub[u];
}
int dfs(int u, int p, int n) {
for (auto [v, w] : tree[u]) {
if (!rem[v] && v != p && sub[v] > n / 2) {
return dfs(v, u, n);
}
}
return u;
}
void process(int u, int p, int depth, long long sum, bool filling) {
if (filling) {
if (mp.find(sum) == mp.end()) {
mp[sum] = depth;
}
else {
mp[sum] = min(mp[sum], depth);
}
}
else {
int need = k - sum;
if (need >= 0) {
if (mp.find(need) != mp.end()) {
if (ans == -1) {
ans = depth + mp[need];
}
else if (depth + mp[need] < ans) {
ans = depth + mp[need];
}
}
}
}
for (auto [v, w] : tree[u]) {
if (v != p && !rem[v]) {
process(v, u, depth + 1, sum + w, filling);
}
}
}
void build(int u, int p) {
int n = dfs(u, p);
int c = dfs(u, p, c);
par[c] = p;
rem[c] = true;
mp.clear();
mp[0] = 0;
for (auto [v, w] : tree[c]) {
if (!rem[v]) {
process(v, c, 1, w, 0);
process(v, c, 1, w, 1);
}
}
for (auto [v, w] : tree[c]) {
if (!rem[v]) {
build(v, u);
}
}
}
public:
CD(const vector<vector<pair<int, long long>>>& t, int k_) {
int n = t.size();
sub.resize(n);
rem.resize(n);
par.resize(n);
tree = t;
k = k_;
build(0, -1);
}
int solve() {
return ans;
}
};
struct edge {
int u, v, w;
};
int best_path(int n, int k, int h[][2], int* l) {
vector<edge> E(n - 1);
for (int i = 0; i < n - 1; i++) {
int u = h[i][0], v = h[i][1];
E[i] = {u, v, -1};
}
for (int i = 0; i < n - 1; i++) {
int ll = l[i];
E[i].w = ll;
}
vector<vector<pair<int, long long>>> t(n);
for (auto e : E) {
t[e.u].push_back({e.v, e.w});
t[e.v].push_back({e.u, e.w});
}
CD g(t, k);
return g.solve();
}
Compilation message (stderr)
race.cpp: In function 'void setIO(std::string)':
race.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
10 | freopen((File_name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | freopen((File_name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |