Submission #484390

#	Time	Username	Problem	Language	Result	Execution time	Memory
484390		Mahdi	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	198 ms	36848 KiB

election_campaign

#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define F first
#define S second
typedef long long ll;
const int N=1e5+5;
int n, q, lg, dp[N], pd[N][18], s[N], f[N], dis[N], h[N];
vector<int>g[N], kd[N], nd;
vector<pair<int, pii>>w[N];

struct fenwick{
    vector<ll>bit=vector<ll>(n, 0);
    void add(int v, int x){
        for(int i=v;i<n;i|=i+1)
            bit[i]+=x;
    }
    void add(int l, int r, int x){
        add(l, x);
        add(r, -x);
    }
    int num(int v){
        ll ans=0;
        for(int i=v;i>=0;i=(i&(i+1))-1)
            ans+=bit[i];
        return ans;
    }
};

void dfs(const int &v, const int &p, int &t){
    s[v]=t++;
    nd.push_back(v);
    for(auto u: g[v]){
        if(u!=p){
            dis[u]=dis[v]+1;
            kd[v].push_back(u);
            pd[u][0]=v;
            for(int i=1;i<=lg;++i)
                pd[u][i]=pd[pd[u][i-1]][i-1];
            dfs(u, v, t);
        }
    }
    f[v]=t;
}

int par(int v, int p){
    int pp;
    while(p>0){
        pp=p&(-p);
        v=pd[v][31-__builtin_clz(pp)];
        p-=pp;
    }
    return v;
}

int lca(int v, int u){
    v=par(v, dis[v]-dis[u]);
    u=par(u, dis[u]-dis[v]);
    if(u==v)
        return v;
    for(int i=lg;i>=0;--i){
        if(pd[v][i]!=pd[u][i]){
            v=pd[v][i];
            u=pd[u][i];
        }
    }
    return pd[v][0];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    lg=31-__builtin_clz(n);
    int v, u;
    for(int i=0;i<n-1;++i){
        cin>>u>>v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    int t=0;
    dfs(0, 0, t);
    cin>>q;
    int x, y;
    while(q--){
        cin>>v>>u>>x;
        y=lca(--v, --u);
        w[y].push_back({x, {v, u}});
    }
    fenwick A;
    for(int i=n-1;i>=0;--i){
        v=nd[i];
        dp[v]=h[v];
        for(auto u: w[v]){
            x=A.num(s[u.S.F])+A.num(s[u.S.S])-2*A.num(s[v])+h[v]+u.F;
            dp[v]=max(dp[v], x);
        }
        h[pd[v][0]]+=dp[v];
        A.add(s[v], f[v], -dp[v]);
        A.add(s[pd[v][0]], f[pd[v][0]], dp[v]);
    }
    cout<<dp[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