/**
* Notes during contest.
*
* ------ A ------
* In the example, (3,7,6,6) is the set of optimal pillars to select. Well, I assume
* that the subset of pillars shall be connected in order? First, sum all costs of
* pillars. The cost of pillars that are used will then be deducted from the total.
* Our dp formula is:
* dp[k] = min( dp[i] + (h[k] - h[i])^2 - c[k])
* = min( (dp[i] + h[i]^2) - 2h[i] * h[k] ) + (h[k]^2 - c[k])
* This looks like sth that can be solved with dynamic convex hull trick. IMO this
* is like the only way to AC this problem. Unfortunately, I don't know how to code
* one using std::set<>, nor do I know LiChao tree. Maybe I'll just head to problem
* C.
*
* ------ B ------
* [S1-2] is solvable with a O(n^2) dp (Z-array + dp). I also have a hunch that we
* can pass [S3] too (#time_limit = 10s). Oh no... I really suck at str processing
* problems... I guess 60 points would be my limit.
*
* ------ C ------
* Can we score some partials here? Clearly, when Tom visits the route, only the
* last node has pigeons, so #pigeons_Tom_meets = #last_node_in_route. OK. Let V be
* the set of nodes in the route, so |V| <= v and
* #pigeons_Tom_meets = sum{ p_i : i is adjacent to at least one node in V
* or i is in V }.
* We also know that #pigeons_Jerry_meets = p_i where i is the first node. This means
* we can solve [S1-3]. Looks like DFS + dp on tree is good enough to solve the whole
* problem!
* --------------------------------- After contest ---------------------------------
* I totally misunderstood the problem... Took me over an hour in the contest.. The
* stuff above is wrong...
*
* Time Complexity 1: O(n^2)
* Time Complexity 2: O(n^2)
* Time Complexity 3: O(n^2 * v)
* Implementation 0.5 (brute-force first)
*/
#include <bits/stdc++.h>
typedef int64_t int_t;
typedef std::vector<int_t> vec;
const int_t INF = 0x3f3f3f3f3f3f3f;
const int_t N_MAX = 1e5;
const int_t V_MAX = 100;
int_t n, v;
std::vector<vec> tree;
vec pigs; // Short form for pigeons. lol
int_t dp[N_MAX][V_MAX + 1];
vec adj_sum;
int_t search(int_t src) {
std::vector<bool> visited(n, false);
visited[src] = true;
std::queue<int_t> bfs_queue;
bfs_queue.emplace(src);
dp[src][0] = 0, dp[src][1] = adj_sum[src];
for (int_t i = 2; i <= v; i++)
dp[src][i] = -INF;
int_t max = 0;
while (!bfs_queue.empty()) {
int_t t = bfs_queue.front();
bfs_queue.pop();
for (int_t k = 0; k <= v; k++)
max = std::max(max, dp[t][k]);
for (int_t neighb : tree[t]) {
if (!visited[neighb]) {
visited[neighb] = true;
for (int_t i = 0; i <= v; i++) {
dp[neighb][i] = dp[t][i];
if (i > 0) {
dp[neighb][i] = std::max(dp[neighb][i],
dp[t][i - 1] + adj_sum[neighb] - pigs[t]);
}
}
bfs_queue.emplace(neighb);
}
}
}
return max;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cin >> n >> v;
tree.assign(n, vec());
pigs.resize(n);
for (int_t k = 0; k < n; k++)
std::cin >> pigs[k];
for (int_t _ = 0; _ < n - 1; _++) {
int_t a, b;
std::cin >> a >> b;
a--, b--;
tree[a].push_back(b);
tree[b].push_back(a);
}
adj_sum.resize(n);
for (int_t k = 0; k < n; k++) {
adj_sum[k] = 0;
for (int_t neighb : tree[k])
adj_sum[k] += pigs[neighb];
}
if (n <= 1000) {
int_t ans = 0;
for (int_t k = 0; k < n; k++)
ans = std::max(ans, search(k));
std::cout << ans << '\n';
} else {
std::cout << search(0) << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
326 ms |
1212 KB |
Output is correct |
| 8 |
Correct |
42 ms |
1200 KB |
Output is correct |
| 9 |
Correct |
32 ms |
1228 KB |
Output is correct |
| 10 |
Correct |
334 ms |
1208 KB |
Output is correct |
| 11 |
Correct |
145 ms |
1204 KB |
Output is correct |
| 12 |
Correct |
63 ms |
1200 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
161 ms |
89156 KB |
Output is correct |
| 2 |
Correct |
134 ms |
89084 KB |
Output is correct |
| 3 |
Correct |
102 ms |
90128 KB |
Output is correct |
| 4 |
Correct |
109 ms |
89228 KB |
Output is correct |
| 5 |
Correct |
177 ms |
89192 KB |
Output is correct |
| 6 |
Correct |
188 ms |
89220 KB |
Output is correct |
| 7 |
Correct |
182 ms |
89172 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
326 ms |
1212 KB |
Output is correct |
| 8 |
Correct |
42 ms |
1200 KB |
Output is correct |
| 9 |
Correct |
32 ms |
1228 KB |
Output is correct |
| 10 |
Correct |
334 ms |
1208 KB |
Output is correct |
| 11 |
Correct |
145 ms |
1204 KB |
Output is correct |
| 12 |
Correct |
63 ms |
1200 KB |
Output is correct |
| 13 |
Correct |
161 ms |
89156 KB |
Output is correct |
| 14 |
Correct |
134 ms |
89084 KB |
Output is correct |
| 15 |
Correct |
102 ms |
90128 KB |
Output is correct |
| 16 |
Correct |
109 ms |
89228 KB |
Output is correct |
| 17 |
Correct |
177 ms |
89192 KB |
Output is correct |
| 18 |
Correct |
188 ms |
89220 KB |
Output is correct |
| 19 |
Correct |
182 ms |
89172 KB |
Output is correct |
| 20 |
Incorrect |
183 ms |
89160 KB |
Output isn't correct |
| 21 |
Halted |
0 ms |
0 KB |
- |
