Submission #754996

#	Time	Username	Problem	Language	Result	Execution time	Memory
754996		ooscode	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	415 ms	66336 KiB

election_campaign

// IN THE NAME OF ALLAH
 
#include<bits/stdc++.h>
 
using namespace std;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define wall cerr << "------------------------------------" << endl
#define pb push_back
#define pob pop_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define scan scanf
#define print printf
#define outs(x) print("%lld " , x)
#define out(x) print("%lld\n" , x)
#define in(x) scan("%lld" , &x)
#define int ll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
#pragma GCC optimize("Ofast")
 
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
typedef pair<pii,int> piii;
typedef pair<pll , ll> plll;
 
const int N = 4e5+10;
const int K = 640+10;
const ll mod = 1e9+7;
const ll INF = 1e9+10;
const int P = 31;
const int lg = 25;

const int delta = 10289;

int par[N][lg];
int p[N];
int h[N];
int dp[N];
int pd[N];
int st[N];
int fn[N];
int oo = 0;

int seg[4*N];
int la[4*N];

vector<int> g[N];

int n , m;

vector<pair<int , pii>> qu[N];

void shift(int v , int tl , int tr) {
    seg[v] += la[v];

    if(tl != tr) {
        la[2*v] += la[v];
        la[2*v+1] += la[v];
    }

    la[v] = 0;
}

void upd(int v , int tl , int tr , int l , int r , int x) {
    shift(v , tl , tr);

    if(l > r)
        return;

    if(tl == l && tr == r) {
        la[v] += x;
        shift(v , tl , tr);
        
        return;
    }

    int tm = (tl + tr)/2;

    upd(2*v , tl , tm , l , min(tm , r) , x);
    upd(2*v+1 , tm+1 , tr , max(l , tm+1) , r , x);

    seg[v] = seg[2*v] + seg[2*v+1];
}

int ask(int v , int tl , int tr , int pos) {
    shift(v , tl , tr);

    if(tl == tr)
        return seg[v];

    int tm = (tl + tr)/2;

    if(tm >= pos)
        return ask(2*v , tl , tm , pos);
    return ask(2*v+1 , tm+1 , tr , pos);
}

void init() {
    for(int i = 1 ; i <= n ; i++)
        par[i][0] = p[i];

    for(int i = 1 ; i < lg ; i++)
        for(int j = 1 ; j <= n ; j++)
            par[j][i] = par[par[j][i-1]][i-1];
}

void dfs(int v , int pr) {
    st[v] = ++oo;
    for(auto u : g[v]) {
        if(u == pr)
            continue;

        p[u] = v;
        h[u] = h[v] + 1;

        dfs(u , v);
    }

    fn[v] = oo;
}

int get_par(int v , int h) {
    for(int i = 0 ; i < lg ; i++)
        if(h & (1ll << i))
            v = par[v][i];

    return v;
}

int lca(int v , int u) {
    if(h[u] > h[v])
        swap(u , v);

    int he = h[v] - h[u];

    if(he) 
        v = get_par(v , he);

    if(v == u)
        return v;

    for(int i = lg-1 ; i >= 0 ; i--)
        if(par[v][i] != par[u][i]) {
            u = par[u][i];
            v = par[v][i];
        }

    return par[v][0];
}

void get(int v , int pr) {
    for(auto u : g[v]) {
        if(u == pr)
            continue;
        
        get(u , v);
        pd[v] += dp[u];
    }

    dp[v] = pd[v];

    for(auto px : qu[v]) {
        int y = px.S.F;
        int u = px.S.S;
        int w = px.F;

        int x = pd[v] + w;

        int f = 0 , e = 0;

        if(u != v)
            f = ask(1 , 1 , n , st[u]);
        if(y != v)
            e = ask(1 , 1 , n , st[y]);

        dp[v] = max(dp[v] , x + f + e);
    }

    upd(1 , 1 , n , st[v] , fn[v] , pd[v] - dp[v]);
}

signed main()
{   
    cin >> n;

    for(int i = 2 ; i <= n ; i++) {
        int v , u;
        cin >> v >> u;

        g[v].pb(u);
        g[u].pb(v);
    }

    dfs(1 , -1);

    init();

    cin >> m;

    for(int i = 1 ; i <= m ; i++) {
        int v , u , w;
        cin >> v >> u >> w;

        int lc = lca(v , u);

        qu[lc].pb({w , {v , u}});
    }

    get(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