Submission #619074

#	Time	Username	Problem	Language	Result	Execution time	Memory
619074		jophyyjh	Chase (CEOI17_chase)	C++14	50 / 100	1449 ms	256516 KiB

chase

/**
 * 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';
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 30