Submission #927444

#	Time	Username	Problem	Language	Result	Execution time	Memory
927444		AlphaMale06	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	141 ms	27476 KiB

election_campaign

#include <bits/stdc++.h>

using namespace std;

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

#define pb push_back
#define F first
#define S second

const int N = 1e5+3;
vector<int> adj[N];
int tin[N], tout[N], h[N];
vector<path> pth[N];
int p[N][18];
int timer=1;
int dp[N][2];
int f[2*N];

void dfs(int v, int par){
    h[v]=h[par]+1;
    tin[v]=timer++;
    p[v][0]=par;
    for(int i=1; i<18; i++){
        p[v][i]=p[p[v][i-1]][i-1];
    }
    for(int to : adj[v]){
        if(to!=par){
            dfs(to, v);
        }
    }
    tout[v]=timer++;
}

bool anc(int a, int b){
    if(tin[a]<=tin[b] && tout[a]>=tout[b])return 1;
    return 0;
}

int lca(int a, int b){
    if(anc(a, b))return a;
    if(anc(b, a))return b;
    for(int i=17; i>=0; i--){
        if(!anc(p[a][i], b)){
            a=p[a][i];
        }
    }
    return p[a][0];
}

void Update(int ind, int add){
    for(int i=ind; i<2*N; i+=i&-i)f[i]+=add;
}

int Get(int ind){
    int ret=0;
    for(int i = ind; i>0; i-=i&-i)ret+=f[i];
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n;
    for(int i=0; i< n-1; i++){
        int a, b;
        cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    dfs(1, 1);
    cin >> m;
    for(int i=0; i< m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        pth[lca(a, b)].pb({a, b, c});
    }
    pair<int, int> order[n];
    for(int i=0; i< n; i++){
        order[i]={h[i+1], i+1};
    }
    sort(order, order+n);
    reverse(order, order+n);
    for(int i=0; i< n; i++){
        int node=order[i].S;
        for(int to : adj[node]){
            if(to!=p[node][0]){
                dp[node][0]+=dp[to][1];
            }
        }
        dp[node][1]=dp[node][0];
        for(path pt : pth[node]){
            dp[node][1]=max(dp[node][1], dp[node][0]+Get(tin[pt.a])+Get(tin[pt.b])-2*Get(tin[node])+pt.c);
        }
        Update(tin[node], dp[node][0]-dp[node][1]);
        Update(tout[node], dp[node][1]-dp[node][0]);
    }
    cout << 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