제출 #619072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
619072		jophyyjh	Chase (CEOI17_chase)	C++14	70 / 100	334 ms	90128 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.
 * 
 * ------ 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';
    }
}

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