Submission #825562

#	Time	Username	Problem	Language	Result	Execution time	Memory
825562		Koyote	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	209 ms	37184 KiB

election_campaign

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

template<class T> bool ckmax(T &u, const T &v) { return u < v ? (u = v, true) : false; }
template<class T> bool ckmin(T &u, const T &v) { return u > v ? (u = v, true) : false; }

struct lca_algo {
//   private:
    int nodeCnt, root;
    vector<int> tin, tout;
    vector<int64_t> depth;
    vector<vector<pair<int, int>>> adj;
    vector<vector<int>> par;
    static int floor_log2(int x) { return x ? 31 - __builtin_clz(x) : -1; }
    void dfs(int u) {
        static int timer = 0;
        tin[u] = ++timer;
        for (int j = 1; j < floor_log2(nodeCnt); j++)
            par[u][j] = par[par[u][j - 1]][j - 1];
        for (auto v : adj[u]) if (v.first != par[u][0]) {
            par[v.first][0] = u;
            depth[v.first] = depth[u] + v.second;
            dfs(v.first);
        }
        tout[u] = ++timer;
    }
  public:
    lca_algo() {}
    lca_algo(int _n, int _root = 0) : nodeCnt(_n), root(_root), tin(_n), tout(_n),
        depth(_n), adj(_n), par(_n, vector<int>(floor_log2(_n), -1)) {}
    void add_edge(int u, int v, int w = 1) {
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    void init() {
        par[root][0] = root;
        depth[root] = 0;
        dfs(root);
    }
    bool is_ancestor(int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }
    int lcaQuery(int u, int v) {
        if (is_ancestor(u, v)) return u;
        if (is_ancestor(v, u)) return v;
        for (int j = floor_log2(nodeCnt) - 1; j >= 0; j--)
            if (!is_ancestor(par[u][j], v)) u = par[u][j];
        return par[u][0];
    }
    int64_t distQuery(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[lcaQuery(u, v)];
    }
};

struct fenwick_tree {
  private:
    int tree_size;
    vector<int64_t> ft1, ft2;
    int lowbit(int i) { return i & -i; }
    int64_t sum(vector<int64_t> &ft, int p) {
        int64_t res = 0; for (; p; p -= lowbit(p)) res += ft[p];
        return res;
    }
    void upd(vector<int64_t> &ft, int p, int64_t v) { for (; p <= tree_size; p += lowbit(p)) ft[p] += v; }
    void update(int p, int64_t v)                   { upd(ft1, p, v), upd(ft2, p, p * v); }
    int64_t query(int p)                            { return (p + 1) * sum(ft1, p) - sum(ft2, p); }
  public:
    fenwick_tree(int _ts) : tree_size(_ts), ft1(_ts + 1), ft2(_ts + 1) {}
    void update(int l, int r, int64_t v)            { assert(l <= r); update(l, v); update(r + 1, -v); }
    int64_t query(int l, int r)                     { assert(l <= r); return query(r) - query(l - 1); }
};

typedef long long ll;

const int N = 1e5 + 2;
int n, m;
vector<array<int, 3>> plans[N];
ll dp[N][2];
lca_algo LCA(N);
fenwick_tree fw(N << 1);

void dfs_dp(int u) {
    for (auto v : LCA.adj[u]) if (v.first != LCA.par[u][0]) {
        dfs_dp(v.first);
        dp[u][0] += dp[v.first][1];
    }
    ckmax(dp[u][1], dp[u][0]);
    for (auto it : plans[u]) {
        int a = it[0], b = it[1], c = it[2];
        ckmax(dp[u][1], c + fw.query(1, LCA.tin[a]) + fw.query(1, LCA.tin[b]) + dp[u][0]);
    }
    fw.update(LCA.tin[u], LCA.tin[u], dp[u][0] - dp[u][1]);
    fw.update(LCA.tout[u], LCA.tout[u], dp[u][1] - dp[u][0]);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v; --u, --v;
        LCA.add_edge(u, v);
    }
    LCA.init();
    cin >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c; --a, --b;
        plans[LCA.lcaQuery(a, b)].push_back({a, b, c});
    }
    dfs_dp(0);
    cout << dp[0][1] << '\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