Submission #484210

#	Time	Username	Problem	Language	Result	Execution time	Memory
484210		Mahfel	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	276 ms	46496 KiB

election_campaign

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int MXN = 2e5 + 20 , LOG = 20;
vector<int> adj[MXN];
int h[MXN] , sz[MXN] , sttime[MXN] , p[LOG][MXN] , zaman;
int from[MXN] , to[MXN] , c[MXN];
ll dp[MXN] , pd[MXN];
vector<int> d[MXN];
int n,m;
struct fenwick {
    int size;
    vector<int> bit;
    fenwick() {
        size = 0;
    }
    void init(int n) {
        size = n;
        bit.assign(size , 0);
    }
    void add(int i , int k) {
        for(; i < size ; i |= (i+1)) {
            bit[i] += k;
        }
    }
    void add(int l , int r , int k) {
        add(l , k); add(r , -k);
    }
    int operator[](int i) {
        int res = 0;
        for(; i >= 0 ; i = (i&(i+1))-1) {
            res += bit[i];
        }
        return res;
    }
} f;

void prep(int v , int dad) {
    p[0][v] = (dad == -1 ? v : dad);
    h[v] = (dad == -1 ? 0 : h[dad]+1);
    sz[v] = 1;
    sttime[v] = zaman++;
    for(auto u : adj[v]) {
        if(u == dad) continue;
        prep(u , v);
        sz[v] += sz[u];
    }
}
int kth_anc(int v , int k) {
    while(k > 0) {
        int x = __builtin_ctz(k);
        v = p[x][v];
        k -= (1 << x);
    }
    return v;
}
int LCA(int v , int u) {
    if(h[v] > h[u]) swap(v , u);
    u = kth_anc(u , h[u]-h[v]);
    if(v == u) return v;
    for(int i = LOG-1 ; i >= 0 ; i--) {
        if(p[i][v] != p[i][u]) {
            v = p[i][v]; u = p[i][u];
        }
    }
    return p[0][v];
}

void DFS(int v , int dad) {
    for(auto u : adj[v]) {
        if(u == dad) continue;
        DFS(u , v); pd[v] += dp[u];
    }
    dp[v] = pd[v];
    for(auto p : d[v]) {
        dp[v] = max(dp[v] , c[p] + pd[v] + f[sttime[from[p]]]-f[sttime[v]] + f[sttime[to[p]]]-f[sttime[v]]);
    }
    f.add(sttime[v] , sttime[v]+sz[v] , pd[v]-dp[v]);
}

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

    cin >> n;
    for(int i = 1 ; i < n ; i++) {
        int v,u; cin >> v >> u;
        adj[v].push_back(u); adj[u].push_back(v);
    }
    prep(1 , -1);
    for(int i = 1 ; i < LOG ; i++) {
        for(int j = 1 ; j <= n ; j++) {
            p[i][j] = p[i-1][p[i-1][j]];
        }
    }

    cin >> m;
    for(int i = 0 ; i < m ; i++) {
        cin >> from[i] >> to[i] >> c[i];
        d[LCA(from[i] , to[i])].push_back(i);
    }
    f.init(n);
    DFS(1 , -1);
    cout << dp[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