Submission #755682

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
755682	2023-06-10T14:39:01 Z	Desh03	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	144 ms	33248 KB

election_campaign

#include <bits/stdc++.h>
using namespace std;

vector<int> dep, dp, dp2;
vector<vector<int>> g, up;
vector<vector<tuple<int, int, int>>> qr;
int t, lg;

void dfs(int u, int p) {
    up[0][u] = p;
    for (int i = 1; i < lg; i++) up[i][u] = up[i - 1][up[i - 1][u]];
    for (int v : g[u])
        if (v ^ p)
            dep[v] = dep[u] + 1, dfs(v, u);
}

int getkth(int u, int k) {
    for (int i = 0; i < lg; i++)
        if (k >> i & 1)
            u = up[i][u];
    return u;
}

void calc_dp(int u, int p) {
    for (int v : g[u])
        if (v ^ p) {
            calc_dp(v, u);
            dp2[u] += dp[v];
        }
    dp[u] = dp2[u];
    for (auto [x, y, w] : qr[u]) {
        int c1 = getkth(x, dep[x] - dep[u] - 1);
        int c2 = getkth(y, dep[y] - dep[u] - 1);
        int cost = w + dp2[x] + dp2[y] + dp2[u];
        if (x ^ u) cost -= dp[c1];
        else cost -= dp2[u];
        if (y ^ u) cost -= dp[c2];
        else cost -= dp2[u];
        dp[u] = max(dp[u], cost);
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int k = dep[u] - dep[v];
    for (int i = 0; i < lg; i++)
        if (k >> i & 1)
            u = up[i][u];
    if (u == v) return u;
    for (int i = lg - 1; i >= 0; i--)
        if (up[i][u] ^ up[i][v])
            u = up[i][u], v = up[i][v];
    return up[0][u];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    while ((1 << lg) <= n) ++lg;
    g.resize(n), up = vector<vector<int>> (lg, vector<int> (n)), dp.resize(n), dp2.resize(n), dep.resize(n), qr.resize(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(0, 0);
    int q;
    cin >> q;
    while (q--) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        qr[lca(u, v)].push_back({u, v, w});
    }
    calc_dp(0, 0);
    cout << dp[0] << '\n';
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Incorrect	1 ms	316 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	114 ms	32964 KB	Output is correct
5	Correct	117 ms	32992 KB	Output is correct
6	Correct	101 ms	32980 KB	Output is correct
7	Correct	106 ms	32868 KB	Output is correct
8	Correct	116 ms	32860 KB	Output is correct
9	Correct	96 ms	32900 KB	Output is correct
10	Correct	116 ms	32868 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	468 KB	Output is correct
4	Correct	114 ms	32964 KB	Output is correct
5	Correct	117 ms	32992 KB	Output is correct
6	Correct	101 ms	32980 KB	Output is correct
7	Correct	106 ms	32868 KB	Output is correct
8	Correct	116 ms	32860 KB	Output is correct
9	Correct	96 ms	32900 KB	Output is correct
10	Correct	116 ms	32868 KB	Output is correct
11	Correct	10 ms	1296 KB	Output is correct
12	Correct	110 ms	33152 KB	Output is correct
13	Correct	121 ms	33220 KB	Output is correct
14	Correct	110 ms	33236 KB	Output is correct
15	Correct	114 ms	33216 KB	Output is correct
16	Correct	112 ms	33196 KB	Output is correct
17	Correct	122 ms	33224 KB	Output is correct
18	Correct	114 ms	33208 KB	Output is correct
19	Correct	96 ms	33248 KB	Output is correct
20	Correct	144 ms	33220 KB	Output is correct