Submission #60366

#	Time	Username	Problem	Language	Result	Execution time	Memory
60366		Benq	Election Campaign (JOI15_election_campaign)	C++11	100 / 100	516 ms	156316 KiB

election_campaign

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;


template<int SZ> struct LCA {
    const int MAXK = 32-__builtin_clz(SZ);
    
    int N, R = 1; // vertices from 1 to N, R = root
    vi edges[SZ];
    int parK[32-__builtin_clz(SZ)][SZ], depth[SZ];
    
    void addEdge(int u, int v) {
        edges[u].pb(v), edges[v].pb(u);
    }
    
    void dfs(int u, int prev){
        parK[0][u] = prev;
        depth[u] = depth[prev]+1;
        for (int v: edges[u]) if (v != prev) dfs(v, u);
    }
    
    void construct() {
        dfs(R, 0);
        FOR(k,1,MAXK) FOR(i,1,N+1)
            parK[k][i] = parK[k-1][parK[k-1][i]];
    }
    
    int lca(int u, int v){
        if (depth[u] < depth[v]) swap(u,v);
        
        F0Rd(k,MAXK) if (depth[u] >= depth[v]+(1<<k))  u = parK[k][u];
        F0Rd(k,MAXK) if (parK[k][u] != parK[k][v]) u = parK[k][u], v = parK[k][v];
        
        if(u != v) u = parK[0][u], v = parK[0][v];
        return u;
    }
    
    int dist(int u, int v) {
        return depth[u]+depth[v]-2*depth[lca(u,v)];
    }
};

LCA<MX> L;

template<class T, int SZ> struct BIT {
    T bit[SZ+1];
    
    BIT() { memset(bit,0,sizeof bit); }
    
    void upd(int k, T val) { // add val to index k
        for( ;k <= SZ; k += (k&-k)) bit[k] += val;
    }
    
    void upd(int l, int r, T val) {
        upd(l,val);
        upd(r+1,-val);
    }
    
    T query(int k) {
        T temp = 0;
        for (;k > 0;k -= (k&-k)) temp += bit[k];
        return temp;
    }
    T query(int l, int r) { return query(r)-query(l-1); } // range query [l,r]
};

BIT<ll,MX> child, path;

int N, nex = 1, rev[MX];
ll val[MX];
vi adj[MX];
vector<array<int,3>> que[MX];

void dfs(int x, int y) {
    pi range; range.f = nex++;
    rev[x] = range.f;
    
    ll cur = 0;
    for (int i: adj[x]) if (i != y) {
        dfs(i,x);
        cur += val[i];
    }
    
    val[x] = cur;
    range.s = nex-1;
    // cout << x << " " << range.f << " " << range.s << "\n";
    
    for (auto a: que[x]) {
        /*cout << "OOH " << x << " " << a[0] << ' ' << a[1] << ' ' << a[2] << ' ' << cur << "\n";
        cout << child.query(a[0])+child.query(a[1]) << "\n";
        cout << -path.query(a[0]) << " " << -path.query(a[1]) << "\n";*/
        val[x] = max(val[x],a[2]+cur
                                +child.query(rev[a[0]])+child.query(rev[a[1]])
                                -path.query(rev[a[0]])-path.query(rev[a[1]]));
    }
    
    // cout << "OH " << x << " " << val[x] << " " << sz(que[x]) << "\n";
    // if (x == 4) cout << "AH " << x << " " << y << " " << val[x] << "\n";
    child.upd(range.f,range.s,cur);
    path.upd(range.f,range.s,val[x]);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    F0R(i,N-1) {
        int x,y; cin >> x >> y;
        adj[x].pb(y), adj[y].pb(x);
        L.addEdge(x,y);
    }
    L.N = N;
    L.construct();
    int M; cin >> M;
    F0R(i,M) {
        int x,y,z; cin >> x >> y >> z;
        // cout << x << " " << y << ' ' << z << ' ' << L.lca(x,y) << "\n";
        que[L.lca(x,y)].pb({x,y,z});
    }
    dfs(1,0);
    cout << val[1];
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

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