/**
* 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.
* [After contest]
* First of all, I think i should've noticed the small size of |w_i| in [S2] allows
* us to store things in a std::set<> for each value of w_i. Now, without a time
* limit, let's try LiChao tree in impl2, and perhaps the dynamic convex hull trick
* optimization in impl3 (notoriously difficult to code...).
*
* ------ 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 }. (Wrong, see below)
* 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... Full solution is a standard dfs + dp on tree in O(nv).
*
* Time Complexity 1: O(n * log(n))
* Time Complexity 2: O(n^2)
* Time Complexity 3: O(n * v^2)
* Implementation 2 (Full solution)
*/
#include <bits/stdc++.h>
typedef int64_t int_t;
typedef std::vector<int_t> vec;
const int_t N_MAX = 1e5;
const int_t V_MAX = 100;
const int_t INF = 0x3f3f3f3f3f3f3f;
struct pair_t {
int_t node, val;
};
inline bool operator<(const pair_t& p1, const pair_t& p2) { return p1.val < p2.val; }
int_t n, v;
std::vector<vec> tree;
vec pigs; // short form for pigeons. lol
vec adj_sum;
int_t dp_up[N_MAX][V_MAX + 1];
int_t dp_down[N_MAX][V_MAX + 1][2];
int_t max_diff = 0;
void dfs(int_t k, int_t parent) {
for (int_t child : tree[k]) {
if (child == parent)
continue;
dfs(child, k);
}
for (int_t i = 0; i <= v; i++) {
dp_up[k][i] = (i == 0 ? int_t(0) : -INF);
dp_down[k][i][0] = (i == 0 ? int_t(0) : -INF), dp_down[k][i][1] = -INF;
}
std::vector<std::vector<pair_t>> downs(v + 1);
for (int_t i = 0; i <= v; i++) {
for (int_t child : tree[k]) {
if (child == parent)
continue;
int_t c = std::max(dp_down[child][i][0], dp_down[child][i][1] - pigs[k]);
dp_down[k][i][0] = std::max(dp_down[k][i][0], c);
downs[i].push_back(pair_t{child, c});
std::sort(downs[i].rbegin(), downs[i].rend());
while (int_t(downs[i].size()) > 2)
downs[i].pop_back();
if (i > 0) {
dp_down[k][i][1] = std::max(dp_down[k][i][1],
dp_down[k][i - 1][0] + adj_sum[k]);
}
}
if (i == 1)
dp_down[k][i][1] = std::max(dp_down[k][i][1], adj_sum[k]);
max_diff = std::max(max_diff, dp_down[k][i][0]);
max_diff = std::max(max_diff, dp_down[k][i][1]);
}
std::vector<pair_t> ups; // exactly i (in [0, v]) -> at most i
for (int_t i = 0; i <= v; i++) {
for (int_t child : tree[k]) {
if (child == parent)
continue;
int_t c = dp_up[child][i];
if (i > 0)
c = std::max(c, dp_up[child][i - 1] + adj_sum[k] - pigs[child]);
dp_up[k][i] = std::max(dp_up[k][i], c);
ups.push_back(pair_t{child, c});
std::sort(ups.rbegin(), ups.rend());
while (int_t(ups.size()) > 2)
ups.pop_back();
}
if (i == 1)
dp_up[k][i] = std::max(dp_up[k][i], adj_sum[k]);
max_diff = std::max(max_diff, dp_up[k][i]);
for (const pair_t& p_up : ups) {
for (const pair_t& p_down : downs[v - i]) {
if (p_up.node != p_down.node)
max_diff = std::max(max_diff, p_up.val + p_down.val);
}
}
}
}
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];
}
dfs(0, -1);
std::cout << max_diff << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
328 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
328 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2800 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2900 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
17 ms |
2724 KB |
Output is correct |
| 11 |
Incorrect |
7 ms |
2712 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1449 ms |
255956 KB |
Output is correct |
| 2 |
Correct |
1261 ms |
256516 KB |
Output is correct |
| 3 |
Correct |
831 ms |
245852 KB |
Output is correct |
| 4 |
Correct |
213 ms |
245636 KB |
Output is correct |
| 5 |
Correct |
1225 ms |
245684 KB |
Output is correct |
| 6 |
Correct |
1227 ms |
245712 KB |
Output is correct |
| 7 |
Correct |
1277 ms |
245748 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
328 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
15 ms |
2800 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2900 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 10 |
Correct |
17 ms |
2724 KB |
Output is correct |
| 11 |
Incorrect |
7 ms |
2712 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
