Submission #1309549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309549		shidou26	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	232 ms	34320 KiB

election_campaign

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

#define endl '\n'
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x << " = " << (x) << "]"

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T1, typename T2> T2 rand(T1 l, T2 r) {
    return uniform_int_distribution<T2>(l, r)(rng);
}
template<typename T1, typename T2> T2 wrand(T1 l, T2 r, int seed) {
    if(seed == 0) return rand(l, r);
    else return (seed > 0 ? max(rand(l, r), wrand(l, r, seed - 1)) : min(rand(l, r), wrand(l, r, seed + 1)));
}

template<typename S, typename T> bool maximize(S &a, T b) {
    if(a < b) {
        a = b;
        return true; 
    }else return false;
}
template<typename S, typename T> bool minimize(S &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }else return false;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tp3;

struct FenwickTree {
    vector<ll> tree;
    FenwickTree (int n) : tree(n + 3) {}

    void update(int p, ll v) {
        for(; p < sz(tree); p += p & -p) tree[p] += v;
    }

    void update(int l, int r, ll x) {
        update(l, x);
        update(r + 1, -x);
    }

    ll get(int p) {
        ll total = 0;
        for(; p > 0; p -= p & -p) total += tree[p];
        return total;
    }
};

void process(int testcase) {
    int N; cin >> N;

    vector<vector<int>> adj(N);
    for(int i = 0; i < N - 1; i++) {
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int log2 = 31 - __builtin_clz(N) + 1, timer = 0;
    vector<int> h(N), tin(N), tout(N);
    vector<vector<int>> par(N, vector<int>(log2));
    function<void(int, int)> dfs = [&](int u, int p) {
        tin[u] = ++timer;
        for(int i = 1; i < log2; i++) 
            par[u][i] = par[par[u][i - 1]][i - 1];

        for(int v : adj[u]) if(v != p) {
            h[v] = h[u] + 1;
            par[v][0] = u;
            dfs(v, u);
        }
        tout[u] = timer;
    };

    dfs(0, -1); 
    function<int(int, int)> lca = [&](int u, int v) {
        if(h[u] < h[v]) swap(u, v);
        for(int i = log2 - 1; i >= 0; i--) 
            if(h[u] - (1 << i) >= h[v]) u = par[u][i];
        if(u == v) return u;
        for(int i = log2 - 1; i >= 0; i--) 
            if(par[u][i] != par[v][i]) {
                u = par[u][i];
                v = par[v][i];
            }
        return par[u][0];
    };

    int Q; cin >> Q;
    vector<vector<tp3>> in(N);
    for(int i = 0; i < Q; i++) {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        // cerr << dbg(lca(a, b) + 1) << dbg(a + 1) << dbg(b + 1) << endl;
        in[lca(a, b)].emplace_back(a, b, c);
    }

    vector<ll> dp(N);
    FenwickTree fen(N);
    function<void(int, int)> work = [&](int u, int p) {
        ll sum_child = 0;
        for(int v : adj[u]) if(v != p) {
            work(v, u);
            sum_child += dp[v];
        }

        dp[u] = sum_child; // not take u        
        for(auto [a, b, c] : in[u]) { // take u
            maximize(dp[u], sum_child + fen.get(tin[a]) + fen.get(tin[b]) + c);
        }
 
        fen.update(tin[u], tout[u], sum_child - dp[u]); // update choice: + not take u - take u
        // cerr << u + 1 << " " << dp[u] << endl;
    };

    work(0, -1);
    cout << dp[0] << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int testcase = 1; // cin >> testcase;
    for(int i = 1; i <= testcase; i++) {
        process(i);
    }

    return 0;
}

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