Submission #370125

#	Time	Username	Problem	Language	Result	Execution time	Memory
370125		Vladth11	Election Campaign (JOI15_election_campaign)	C++14	0 / 100	310 ms	37436 KiB

election_campaign

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
//#include "shoes.h"

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 100001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 316;
const ll nr_of_bits = 20;
const long double eps = 0.0000000000000001;

vector <ll> v[NMAX];
ll dp[NMAX][nr_of_bits + 1];
ll n;
ll lvl[NMAX];
pii timpi[NMAX];
ll stamp;
ll DP[NMAX];

ll aib[NMAX * 2 + 1];
void update(ll node, ll v) {
    for(ll i = node; i <= 2 * n; i += i&(-i)){
        aib[i] += v;
    }
}

ll query(ll node){
    ll v = 0;
    for(ll i = node; i > 0; i -= i&(-i)){
        v += aib[i];
    }
    return v;
}

struct queries {
    ll a, b, la, lb, val;
};

vector <queries> events[NMAX];

bool isParent(ll a, ll b) {
    return (timpi[a].first <= timpi[b].first && timpi[b].second <= timpi[a].second);
}

void DFS(ll node, ll p) {
    dp[node][0] = p;
    timpi[node].first = ++stamp;
    lvl[node] = lvl[p] + 1;
    for(auto x : v[node]) {
        if(x == p)
            continue;
        DFS(x, node);
    }
    timpi[node].second = ++stamp;
}

ll LCA(ll a, ll b) {
    if(lvl[a] > lvl[b])
        swap(a, b);
    ll r = a, pas = nr_of_bits;
    while(pas >= 0) {
        ll nxt = dp[r][pas];
        if(nxt != 0 && !isParent(nxt, b))
            r = nxt;
        pas--;
    }
    if(!isParent(r, b))
        r = dp[r][0];
    return r;
}
ll sol;

void Compute(ll node, ll p){
    ll sum = 0;
    for(auto x : v[node]){
        if(x == p)
            continue;
        Compute(x, node);
        sum += DP[x];
    }
    ll maxim = 0;
    for(auto x : events[node]){
        ll cost = sum + x.val;
        if(x.la != -1){
            ///poate facem ceva mai clean aici
            cost += (query(timpi[x.a].first) - query(timpi[node].first));
        }
        if(x.lb != -1){
            cost += (query(timpi[x.b].first) - query(timpi[node].first));
        }
        maxim = max(maxim, cost);
    }
    DP[node] = maxim;
    sol = max(sol, DP[node]);
    ll val = sum - DP[node];
    update(timpi[node].first, val);
    update(timpi[node].second, -val);
}

int main() {
    ll i, j;
    cin >> n;
    for(i = 1; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    DFS(1, 0);
    for(j = 1; j <= nr_of_bits; j++) {
        for(i = 1; i <= n; i++) {
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    ll m;
    cin >> m;
    while(m--) {
        ll a, b, la, lb, val;
        cin >> a >> b >> val;
        ll lca = LCA(a, b);
        if(lvl[a] == lvl[lca]) {
            la = -1;
        } else {
            ll r = a, pas = nr_of_bits;
            while(pas >= 0) {
                ll nxt = dp[r][pas];
                if(nxt != 0 && !isParent(nxt, lca))
                    r = nxt;
                pas--;
            }
            la = r;
        }
        if(lvl[b] == lvl[lca]) {
            lb = -1;
        } else {
            ll r = b, pas = nr_of_bits;
            while(pas >= 0) {
                ll nxt = dp[r][pas];
                if(nxt != 0 && !isParent(nxt, lca))
                    r = nxt;
                pas--;
            }
            lb = r;
        }
        events[lca].push_back({a, b, la, lb, val});
    }
    Compute(1, 0);
    cout << sol;
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40