This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define INF 0x3f3f3f3f
const int MAXN = 2e5;
const int MAXK = 1e6 + 6;
int sz[MAXN];
vector<pair<int,int>> G[MAXN];
bitset<MAXN> viz;
void find_size(int u, int parent) {
sz[u] = 1;
for (auto v : G[u])
if (v.first != parent && !viz[v.first]) {
find_size(v.first, u);
sz[u] += sz[v.first];
}
}
int find_centroid(int u, int parent, int n) {
for (auto v : G[u])
if (v.first != parent && !viz[v.first] && sz[v.first] > (n >> 1))
return find_centroid(v.first, u, n);
return u;
}
int ans = INF, k, best_prev[MAXK], best[MAXK], tree_ans;
vector<int> sums;
void min_self(int &a, int b) {
a = min(a, b);
}
void find_paths(int u, int parent, int sum, int depth) {
if (sum > k)
return;
sums.emplace_back(sum);
min_self(best[sum], depth);
min_self(tree_ans, best_prev[k - sum] + best[sum]);
if (sum == k)
return;
for (auto v : G[u])
if (v.first != parent && !viz[v.first])
find_paths(v.first, u, sum + v.second, depth + 1);
}
int solve_tree(int u) {
tree_ans = INF;
vector<int> all_sums;
for (auto v : G[u])
if (!viz[v.first]) {
find_paths(v.first, u, v.second, 1);
for (int s : sums) {
min_self(best_prev[s], best[s]);
best[s] = INF;
all_sums.emplace_back(s);
}
sums.clear();
}
for (int s : all_sums)
best_prev[s] = INF;
return tree_ans;
}
int build(int u, int parent) {
find_size(u, -1);
int c = find_centroid(u, -1, sz[u]);
viz[c] = true;
int ans = solve_tree(c);
for (auto v : G[c])
if (!viz[v.first])
ans = min(ans, build(v.first, c));
return ans;
}
int best_path(int N, int K, int H[][2], int L[]) {
for (int i = 0; i < N - 1; ++i) {
G[H[i][0]].emplace_back(H[i][1], L[i]);
G[H[i][1]].emplace_back(H[i][0], L[i]);
}
k = K;
for (int s = 1; s <= k; ++s)
best_prev[s] = best[s] = INF;
min_self(ans , build(0, -1));
if (ans == INF)
ans = -1;
return ans;
}
Compilation message (stderr)
race.cpp:5:1: error: 'vector' does not name a type
5 | vector<pair<int,int>> G[MAXN];
| ^~~~~~
race.cpp:6:1: error: 'bitset' does not name a type
6 | bitset<MAXN> viz;
| ^~~~~~
race.cpp: In function 'void find_size(int, int)':
race.cpp:10:17: error: 'G' was not declared in this scope
10 | for (auto v : G[u])
| ^
race.cpp:11:31: error: 'viz' was not declared in this scope
11 | if (v.first != parent && !viz[v.first]) {
| ^~~
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:18:17: error: 'G' was not declared in this scope
18 | for (auto v : G[u])
| ^
race.cpp:19:31: error: 'viz' was not declared in this scope
19 | if (v.first != parent && !viz[v.first] && sz[v.first] > (n >> 1))
| ^~~
race.cpp: At global scope:
race.cpp:25:1: error: 'vector' does not name a type
25 | vector<int> sums;
| ^~~~~~
race.cpp: In function 'void min_self(int&, int)':
race.cpp:28:7: error: 'min' was not declared in this scope
28 | a = min(a, b);
| ^~~
race.cpp: In function 'void find_paths(int, int, int, int)':
race.cpp:34:3: error: 'sums' was not declared in this scope; did you mean 'sum'?
34 | sums.emplace_back(sum);
| ^~~~
| sum
race.cpp:39:17: error: 'G' was not declared in this scope
39 | for (auto v : G[u])
| ^
race.cpp:40:31: error: 'viz' was not declared in this scope
40 | if (v.first != parent && !viz[v.first])
| ^~~
race.cpp: In function 'int solve_tree(int)':
race.cpp:46:3: error: 'vector' was not declared in this scope
46 | vector<int> all_sums;
| ^~~~~~
race.cpp:46:10: error: expected primary-expression before 'int'
46 | vector<int> all_sums;
| ^~~
race.cpp:47:17: error: 'G' was not declared in this scope
47 | for (auto v : G[u])
| ^
race.cpp:48:10: error: 'viz' was not declared in this scope
48 | if (!viz[v.first]) {
| ^~~
race.cpp:50:20: error: 'sums' was not declared in this scope
50 | for (int s : sums) {
| ^~~~
race.cpp:53:9: error: 'all_sums' was not declared in this scope
53 | all_sums.emplace_back(s);
| ^~~~~~~~
race.cpp:55:7: error: 'sums' was not declared in this scope
55 | sums.clear();
| ^~~~
race.cpp:57:16: error: 'all_sums' was not declared in this scope
57 | for (int s : all_sums)
| ^~~~~~~~
race.cpp: In function 'int build(int, int)':
race.cpp:65:3: error: 'viz' was not declared in this scope
65 | viz[c] = true;
| ^~~
race.cpp:67:17: error: 'G' was not declared in this scope
67 | for (auto v : G[c])
| ^
race.cpp:69:13: error: 'min' was not declared in this scope
69 | ans = min(ans, build(v.first, c));
| ^~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:75:5: error: 'G' was not declared in this scope
75 | G[H[i][0]].emplace_back(H[i][1], L[i]);
| ^