Submission #954462

#	Time	Username	Problem	Language	Result	Execution time	Memory
954462		Rifal	Election Campaign (JOI15_election_campaign)	C++14	100 / 100	246 ms	48180 KiB

election_campaign

#include <bits/stdc++.h>
#include <fstream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define mod 1000000007
#define INF 1000000000
#define INF2 2000000000
///#define cin fin
///#define cout fout
using namespace std;
double const EPS = 1e-14;
const int P = 1007;
typedef long long ll;
///ofstream fout("herding.out");
///ifstream fin("herding.in");
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
const int N = 1e5 + 5;
const int M = 2e5 + 5;
struct Plan {
    ll a, b, c;
};
pair<ll,ll> seg[M*4];
vector<int> v[N];
vector<Plan> plan[N];
ll dp[N], sum[N];
int st[N], ed[N];
int dep[N], lca[N][30];
int tim = 1;

void Update(int x, int l, int r, int pos, pair<ll,ll> val) {
    if(l == r) {
        seg[x].first = val.first;
        seg[x].second = val.second;
    }
    else {
        int mid = (l+r)/2;
        if(pos <= mid) Update(x*2,l,mid,pos,val);
        else Update(x*2+1,mid+1,r,pos,val);
        seg[x].first = seg[x*2].first+seg[x*2+1].first;
        seg[x].second = seg[x*2].second+seg[x*2+1].second;
    }
}

pair<ll,ll> Sum(int x, int l, int r, int L, int R) {
    if(r < L || l > R) {
        return {0,0};
    }
    else if(l >= L && r <= R) {
        return seg[x];
    }
    else {
        int mid = (l+r)/2;
        pair<ll,ll> val1 = Sum(x*2,l,mid,L,R), val2 = Sum(x*2+1,mid+1,r,L,R);
        pair<ll,ll> val3;
        val3.first = val1.first+val2.first;
        val3.second = val1.second+val2.second;
        return val3;
    }
}

void dfs(int s, int p) {
    for(int i = 1; (1<<i) <= dep[s]; i++) {
        lca[s][i] = lca[lca[s][i-1]][i-1];
    }
    st[s] = tim; tim++;
    for(auto i : v[s]) {
        if(i != p) {
            dep[i] += dep[s]+1;
            lca[i][0] = s;
            dfs(i,s);
        }
    }
    ed[s] = tim; tim++;
}

void sol(int s, int p) {
    for(auto i : v[s]) {
        if(i != p) {
            sol(i,s);
            sum[s] += dp[i];
        }
    }
    dp[s] = max(dp[s],sum[s]);
    for(auto i : plan[s]) {
        int a = i.a, b = i.b;
        if(s == a || s == b) {
            if(st[a] > st[b]) swap(a,b);
            pair<ll,ll> tota = Sum(1,1,M,1,st[a]), totb = Sum(1,1,M,1,st[b]);
            ll tot1 = totb.second-tota.second+sum[s], tot2 = totb.first-tota.first;
            dp[s] = max(dp[s],tot1-tot2+i.c);
        }
        else {
            pair<ll,ll> tota = Sum(1,1,M,1,st[a]), totb = Sum(1,1,M,1,st[b]), tots = Sum(1,1,M,1,st[s]);
            ll tot1 = totb.second+tota.second - (2ll*tots.second) + sum[s], tot2 = totb.first+tota.first - (2ll*tots.first);
            dp[s] = max(dp[s],tot1-tot2+i.c);
        }
    }
    pair<ll,ll> val; val.first = dp[s], val.second = sum[s];
    Update(1,1,M,st[s],val);
    val.first *= -1ll; val.second *= -1ll;
    Update(1,1,M,ed[s],val);
}

int fin(int x, int y) {
    if(dep[x] < dep[y]) swap(x,y);
    int pw2 = 0;
    while(dep[x]-dep[y] > 0) {
        if(((dep[x]-dep[y])&(1<<pw2)) > 0) {
            x = lca[x][pw2];
        }
        pw2++;
    }
    while(x != y) {
        pw2 = 29;
        while(lca[x][pw2] == lca[y][pw2] && pw2 > 0) pw2--;
        x = lca[x][pw2];
        y = lca[y][pw2];
    }
    return x;
}

int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n; cin >> n;
    for(int i = 0; i < n-1; i++) {
        int a, b; cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0);
    int m; cin >> m;
    for(int i = 0; i < m; i++) {
        Plan cur; cin >> cur.a >> cur.b >> cur.c;
        int d = fin(cur.a,cur.b);
        plan[d].push_back(cur);
    }
    sol(1,0);
    cout << dp[1] << endl;
    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