Submission #1150031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150031		andrewp	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	142 ms	68676 KiB

election_campaign

//Dedicated to my love, ivaziva
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(a) ((int)a.size()) 
const int N=1e6+5;   

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

int n, m, up[N][20], dep[N], tin[N], tout[N], tajm=1, ft[N]; 
vector<int> g[N]; 
ll dp[N][2]; 
vector<node> pom[N];

void dfs(int x, int p) {
    dep[x]=dep[p]+1;
    tin[x]=tajm++;
    up[x][0]=p;
    for (int i=1; i<20; i++) 
        up[x][i]=up[up[x][i-1]][i-1]; 
    for (int u:g[x]) {
        if (u!=p) 
            dfs(u, x);
    }
    tout[x]=tajm++;
} 

int raise(int x, int y) {
    int z=0;
    while (y) {
        if (y&1) 
            x=up[x][z];
        z++;
        y>>=1;
    }
    return x;
}

array<int, 3> lca(int a, int b) {
    if (dep[a]>dep[b]) 
        swap(a, b);
    int x=dep[b]-dep[a];
    int ob=b; 
    b=raise(b, x);
    if (a==b) 
        return {a, raise(ob, x-1), -1};
    for (int i=19; i>=0; i--) {
        if (up[a][i]!=up[b][i]) {
            a=up[a][i];
            b=up[b][i];
        }
    } 
    return {up[a][0], a, b}; 
} 

void modify(int i, int val) {
    while (i<N) {
        ft[i]+=val;
        i+=i&(-i);
    }
}

ll get(int i) {
    int ret=0;
    while (i) {
        ret+=ft[i];
        i-=i&(-i);
    }
    return ret; 
}
 
int main () {
    ios::sync_with_stdio(false), cin.tie(0);
        
    cin >> n;
    for (int i=1; i<n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs(1, 0);  
    int q;
    cin >> q;
    while (q--) {
        int a, b, c;
        cin >> a >> b >> c; 
        array<int, 3> LCA=lca(a, b);    
        pom[LCA[0]].pb({a, b, c}); 
    } 
    for (int i=1; i<=n; i++) 
        dp[i][0]=0, dp[i][1]=0; 
    pii ord[n];
    for (int i=1; i<=n; i++) 
        ord[i-1]=make_pair(dep[i], i);
    sort(ord, ord+n);
    reverse(ord, ord+n);
    for (int i=0; i<n; i++) {
        int x=ord[i].second;
        for (int u:g[x]) {
            if (u!=up[x][0]) 
                dp[x][0]+=dp[u][1];
        } 
        for (auto z:pom[x])  
            dp[x][1]=max(dp[x][1], dp[x][0]+get(tin[z.a])+get(tin[z.b])-2*get(tin[x])+z.c); 
        dp[x][1]=max(dp[x][1], dp[x][0]);
        modify(tin[x], dp[x][0]-dp[x][1]);
        modify(tout[x], dp[x][1]-dp[x][0]);
    } 
    cout << max(dp[1][0], dp[1][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