Submission #419663

#	Time	Username	Problem	Language	Result	Execution time	Memory
419663		tengiz05	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	270 ms	33732 KiB

election_campaign

#include <bits/stdc++.h>
constexpr int N = 1e5;
struct segtree{
    std::vector<int> t;
    int n;
    segtree(int n) : n(n), t(2 * n) { }
    void update(int p, int val) {
        for (t[p += n] = val; p > 1; p >>= 1) {
            t[p >> 1] = t[p] + t[p ^ 1];
        }
    }
    int get(int l, int r) {
        int res = 0;
        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l % 2 == 1) res += t[l++];
            if (r % 2 == 0) res += t[r--];
        }
        return res;
    }
} dpsum(N), childsum(N);
std::vector<int> e[N];
int n, m, in[N], out[N], up[N][20], timeStamp, siz[N], heavy[N], D[N], par[N], head[N], pos[N];
void precalc(int u, int p, int d = 0) {
    par[u] = p;
    D[u] = d;
    siz[u] = 1;
    in[u] = timeStamp++;
    up[u][0] = p;
    for (int i = 1; i < 20; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    int mx_size = 0;
    for (auto v : e[u]) {
        if (v != p) {
            precalc(v, u, d + 1);
            siz[u] += siz[v];
            if (mx_size < siz[v]) {
                mx_size = siz[v];
                heavy[u] = v;
            }
        }
    }
    out[u] = timeStamp;
}
bool is(int u, int v) { return in[u] <= in[v] && out[u] >= out[v]; }
int lca(int u, int v) {
    if (is(u, v)) return u;
    if (is(v, u)) return v;
    for (int i = 19; i >= 0; i--) {
        if (!is(up[u][i], v)) {
            u = up[u][i];
        }
    }
    return up[u][0];
}
void dfs(int u, int h) {
    head[u] = h;
    pos[u] = timeStamp++;
    if (~heavy[u]) {
        dfs(heavy[u], h);
    }
    for (auto v : e[u]) {
        if (v != par[u] && v != heavy[u]) {
            dfs(v, v);
        }
    }
}
int queryChild(int u, int v) {
    int res = 0;
    for (; head[u] != head[v]; v = par[head[v]]) {
        if (D[head[u]] > D[head[v]]) {
            std::swap(u, v);
        }
        res += childsum.get(pos[head[v]], pos[v]);
    }
    if (D[u] > D[v]) {
        std::swap(u, v);
    }
    res += childsum.get(pos[u], pos[v]);
    return res;
}
int queryDp(int u, int v) {
    int res = 0;
    for (; head[u] != head[v]; v = par[head[v]]) {
        if (D[head[u]] > D[head[v]]) {
            std::swap(u, v);
        }
        res += dpsum.get(pos[head[v]], pos[v]);
    }
    if (D[u] > D[v]) {
        std::swap(u, v);
    }
    res += dpsum.get(pos[u], pos[v]);
    return res;
}
std::vector<std::tuple<int, int, int>> q[N];
int dp[N];
void calc(int u) {
    int chsum = 0;
    for (auto v : e[u]) {
        if (v != par[u]) {
            calc(v);
            chsum += dp[v];
        }
    }
    childsum.update(pos[u], chsum);
    dp[u] = chsum;
    for (auto [a, b, c] : q[u]) {
        int res = 0;
        res += queryChild(a, b);
        res -= queryDp(a, b);
        res += c;
        dp[u] = std::max(dp[u], res);
    }
    dpsum.update(pos[u], dp[u]);
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    memset(heavy, -1, sizeof heavy);
    precalc(0, 0);
    timeStamp = 0;
    dfs(0, 0);
    std::cin >> m;
    for (int i = 0; i < m; i++) {
        int u, v, c;
        std::cin >> u >> v >> c;
        u--;
        v--;
        q[lca(u, v)].emplace_back(u, v, c);
    }
    calc(0);
    std::cout << dp[0] << "\n";
    return 0;
}

Compilation message (stderr)

election_campaign.cpp: In constructor 'segtree::segtree(int)':
election_campaign.cpp:5:9: warning: 'segtree::n' will be initialized after [-Wreorder]
    5 |     int n;
      |         ^
election_campaign.cpp:4:22: warning:   'std::vector<int> segtree::t' [-Wreorder]
    4 |     std::vector<int> t;
      |                      ^
election_campaign.cpp:6:5: warning:   when initialized here [-Wreorder]
    6 |     segtree(int n) : n(n), t(2 * n) { }
      |     ^~~~~~~

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