Submission #1229283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229283		avohado	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	112 ms	34888 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
vector<int> g[maxn];
int  bit[maxn], up[maxn][20], n, m, timer=1, in[maxn], out[maxn];
long long dp[maxn][2];
vector<pair<pair<int, int>,int>> o[maxn];
void dfs1(int u, int p){
    in[u]=timer;timer++;
    up[u][0]=p;
    for(int i=1; i<20; i++){
        up[u][i]=up[up[u][i-1]][i-1];
    }
    for(auto i:g[u]){
        if(i!=p){
            dfs1(i, u);
        }
    }
    out[u]=timer;
}
int lca(int u, int v){
    int p, l;
    if(in[u]>in[v]){
     p=u;l=v;}
    else{
    p=v;l=u;}
    for(int i=19; i>=0; i--){
        if(in[up[p][i]]>in[l]){
            p=up[p][i];
        }
    }
    return up[p][0];
}
long long get(int l){
    int i=l;
    long long ans=0;
    while(i!=0){
        ans+=bit[i];
        i-=(i&-i);
    }
    return ans;
}
void upd(int i, int x){
    int l=i;
    while(l<=n){
        bit[l]+=x;
        l+=(l&-l);
    }
}
void dfs(int u, int p){
    for(auto v:g[u]){
        if(v!=p){
            dfs(v, u);
            dp[u][0]+=dp[v][1];
        }
    }
    dp[u][1]=dp[u][0];
    for(auto i:o[u]){
        dp[u][1]=max(dp[u][1], dp[u][0]+get(in[i.f.s])+get(in[i.f.f])+i.s);
    }
    upd(in[u], dp[u][0]-dp[u][1]);
    upd(out[u], dp[u][1]-dp[u][0]);
}
void solve(){
    cin >> n;
    for(int i=1; i<n; i++){
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    dfs1(1, 0);
    cin >> m;
    for(int i=0; i<m; i++){
        int u, v, p, c;
        cin >> u >> v >> c;
        p=lca(u, v);
        o[p].push_back({{u, v}, c});
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]);
}
int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int t=1;
    //cin >> t;
    while(t--){
        solve();
        cout << "\n";
    }
    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