Submission #1180646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180646		Tymond	Election Campaign (JOI15_election_campaign)	C++20	100 / 100	213 ms	33888 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

const int MAXN = 1e5 + 7;
const int BASE = (1 << 19);
const int MAXK = 20;
int jump[MAXK][MAXN];
int dep[MAXN];
ll dp[MAXN][2];
int parent[MAXN];
vi g[MAXN];
int in[MAXN];
int out[MAXN];
vector<pair<pii, int>> vec[MAXN];
ll tree[2][2 * BASE];
int n, m, c;

int lca(int u, int v){
    if(dep[u] > dep[v]){
        swap(u, v);
    }
    
    for(int j = MAXK - 1; j >= 0; j--){
        if(dep[v] - (1 << j) >= dep[u]){
            v = jump[j][v];
        }
    }
    
    if(u == v)return u;
    
    for(int j = MAXK - 1; j >= 0; j--){
        if(jump[j][u] != jump[j][v]){
            u = jump[j][u];
            v = jump[j][v];
        }
    }
    return parent[v];
}

void dfs(int v, int p, int d){
    parent[v] = p;
    dep[v] = d;
    in[v] = ++c;
    for(auto u : g[v]){
        if(u != p){
            dfs(u, v, d + 1);
        }
    }
    out[v] = c;
}

void init(){
    c = 0;
    dfs(1, 1, 0);
    for(int i = 1; i <= n; i++){
        jump[0][i] = parent[i];
    }
    for(int j = 1; j < MAXK; j++){
        for(int i = 1; i <= n; i++){
            jump[j][i] = jump[j - 1][jump[j - 1][i]];
        }
    }
}

int t;
void upd(int ind, ll val){
    ind += BASE;
    while(ind > 0){
        tree[t][ind] += val;
        ind /= 2;
    }
}

ll query(int v, int l, int p, int a, int b){
    if(p < a || b < l){
        return 0LL;
    }
    if(a <= l && p <= b){
        return tree[t][v];
    }

    int mid = (l + p) / 2;
    return query(2 * v, l, mid, a, b) + query(2 * v + 1, mid + 1, p, a, b);
}

void dfs2(int v, int p){
    dp[v][0] = dp[v][1] = 0LL;
    for(auto u : g[v]){
        if(u == p){
            continue;
        }
        dfs2(u, v);
        dp[v][0] += max(dp[u][0], dp[u][1]);
    }

    for(auto ele : vec[v]){
        int a = ele.fi.fi;
        int b = ele.fi.se;
        int C = ele.se;
        t = 0;
        ll add = query(1, 0, BASE - 1, 0, in[a]) + query(1, 0, BASE - 1, 0, in[b]);
        t = 1;
        add = (ll)add - query(1, 0, BASE - 1, 0, in[a]) - query(1, 0, BASE - 1, 0, in[b]);
        //cout << "PATH:\n";
        //cout << v << ' ' << a << ' ' << b << ' ' << C << ' ' << add << '\n';
        //cout << in[a] << ' ' << in[b] << '\n';
        dp[v][1] = max(dp[v][1],(ll) dp[v][0] + add + C);
    }
    //cout << "FINISHED V: " << v << '\n';
    //cout << in[v] << ' ' << out[v] << '\n';
   // cout << v << ' ' << dp[v][0] << ' ' << dp[v][1] << '\n';
    t = 0;
    upd(in[v], dp[v][0]);
    upd(out[v] + 1, -dp[v][0]);
    t = 1;
    upd(in[v], max(dp[v][0], dp[v][1]));
    upd(out[v] + 1, -max(dp[v][0], dp[v][1]));
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin >> n;
    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        g[a].pb(b);
        g[b].pb(a);
    }

    init();
    cin >> m;
    for(int i = 1; i <= m; i++){
        int a, b, C;
        cin >> a >> b >> C;
        //cout << lca(a, b) << '\n';
        vec[lca(a, b)].pb(mp(mp(a, b), C));
    }
    
    dfs2(1, 1);
    cout << max(dp[1][0], dp[1][1]) << '\n';
    
    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