Submission #1210581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210581		Double_Slash	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	200 ms	35688 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;
 
int n, m, depth[100001], inc[100001], exc[100001], jump[100001][17], mem[100001][17];
vector<int> adj[100001];
vector<array<int, 3>> paths[100001];

void dfs(int i) {
    for (int j: adj[i]) {
        if (j == jump[i][0]) continue;
        depth[j] = depth[jump[j][0] = i] + 1;
        dfs(j);
    }
}

int dp(int i, int k) { return ~mem[i][k] ? mem[i][k] : mem[i][k] = dp(i, k - 1) + dp(jump[i][k - 1], k - 1); }

void dfs2(int i) {
    for (int j: adj[i]) {
        if (j == jump[i][0]) continue;
        dfs2(j);
        exc[i] += inc[j];
    }
    inc[i] = exc[i];
    for (auto [a, b, c]: paths[i]) {
        c += exc[i];
        for (int k = 17; k--;) {
            if (depth[jump[a][k]] >= depth[i]) {
                c -= dp(a, k);
                a = jump[a][k];
            }
            if (depth[jump[b][k]] >= depth[i]) {
                c -= dp(b, k);
                b = jump[b][k];
            }
        }
        inc[i] = max(inc[i], c);
    }
    mem[i][0] = inc[i] - exc[i];
}

int main() {
    cin >> n;
    for (int i = n; --i;) {
        int a, b;
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    dfs(depth[1] = 1);
    for (int k = 1; k < 17; ++k) {
        for (int i = 1; i <= n; ++i) jump[i][k] = jump[jump[i][k - 1]][k - 1];
    }
    cin >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        int x = a, y = b;
        if (depth[x] > depth[y]) swap(x, y);
        for (int k = 17; k--;) {
            if (depth[jump[y][k]] >= depth[x]) y = jump[y][k];
        }
        for (int k = 17; k--;) {
            if (jump[x][k] != jump[y][k]) x = jump[x][k], y = jump[y][k];
        }
        if (x != y) x = jump[x][0];
        paths[x].push_back({a, b, c});
    }
    memset(mem, -1, sizeof mem);
    dfs2(1);
    cout << inc[1];
}

• Subtask 1: 10 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 30 / 30
• Subtask 5: 10 / 10
• Subtask 6: 40 / 40