Submission #109680

#	Time	Username	Problem	Language	Result	Execution time	Memory
109680		popovicirobert	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	402 ms	35408 KiB

election_campaign

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

struct Fenwick {
    vector <ll> aib;
    int n;

    inline void init(int _n) {
        n = _n;
        aib.resize(n + 1);
    }

    inline void update(int pos, int val) {
        for(int i = pos; i <= n; i += lsb(i)) {
            aib[i] += val;
        }
    }

    inline ll query(int pos) {
        ll ans = 0;
        for(int i = pos; i > 0; i -= lsb(i)) {
            ans += aib[i];
        }
        return ans;
    }

    inline ll sum(int l, int r) {
        return query(r) - query(l);
    }
};

const int MAXN = (int) 1e5;
const int LOG = 17;

vector <int> g[MAXN + 1];
int anc[MAXN + 1][LOG + 1], lvl[MAXN + 1];
int first[MAXN + 1], last[MAXN + 1], sz;


void dfs(int nod, int par) {

    first[nod] = ++sz;
    anc[nod][0] = par;
    for(int bit = 1; bit <= LOG; bit++) {
        anc[nod][bit] = anc[anc[nod][bit - 1]][bit - 1];
    }

    lvl[nod] = lvl[par] + 1;
    for(auto it : g[nod]) {
        if(it != par) {
            dfs(it, nod);
        }
    }

    last[nod] = ++sz;
}

inline int get_lca(int x, int y) {
    if(lvl[x] > lvl[y]) {
        swap(x, y);
    }

    for(int bit = 0; bit <= LOG; bit++) {
        if((lvl[y] - lvl[x]) & (1 << bit)) {
            y = anc[y][bit];
        }
    }

    if(x == y) {
        return x;
    }

    for(int bit = LOG; bit >= 0; bit--) {
        if(anc[x][bit] != anc[y][bit]) {
            x = anc[x][bit];
            y = anc[y][bit];
        }
    }

    return anc[x][0];
}

inline int get_anc(int nod, int len) {
    for(int bit = 0; bit <= LOG; bit++) {
        if(len & (1 << bit)) {
            nod = anc[nod][bit];
        }
    }

    return nod;
}

inline ll get_sum(int x, int y, Fenwick &fen) {
    x = first[x], y = first[y];

    if(x > y) {
        swap(x, y);
    }

    return fen.sum(x, y);

}

struct Query {
    int a, b, c;
};

vector <Query> qry[MAXN + 1];

Fenwick fen_dp, fen_sum;
ll dp[MAXN + 1], sum[MAXN + 1];


void solve(int nod, int par) {

    for(auto it : g[nod]) {
        if(it != par) {
            solve(it, nod);
            sum[nod] += dp[it];
        }
    }

    fen_sum.update(first[nod], sum[nod]);
    fen_sum.update(last[nod], -sum[nod]);

    dp[nod] = sum[nod];

    for(auto it : qry[nod]) {
        int a = it.a, b = it.b, c = it.c;
        ll cur = get_sum(a, nod, fen_sum) + get_sum(b, nod, fen_sum) - get_sum(a, nod, fen_dp) - get_sum(b, nod, fen_dp);
        dp[nod] = max(dp[nod], cur + sum[nod] + c);
    }

    fen_dp.update(first[nod], dp[nod]);
    fen_dp.update(last[nod], -dp[nod]);

}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, n, m;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;

    for(i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);

    cin >> m;

    for(i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        qry[get_lca(a, b)].push_back({a, b, c});
    }

    fen_dp.init(2 * n), fen_sum.init(2 * n);
    solve(1, 0);

    cout << dp[1];

    //cin.close();
    //cout.close();
    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