Submission #297617

#	Time	Username	Problem	Language	Result	Execution time	Memory
297617		limabeans	Election Campaign (JOI15_election_campaign)	C++17	30 / 100	1057 ms	155128 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;
const int LOG = 20;
const ll inf = 1e18;

struct MaxLazySegmentTree {
    vector<ll> t, o;
    void init(int n) {
	n += 10;
	t.resize(4*n);
	o.resize(4*n);
    }
    
    void push(int v) {
	t[2*v]+=o[v];
	t[2*v+1]+=o[v];
	o[2*v]+=o[v];
	o[2*v+1]+=o[v];
	o[v]=0;
    }
 
    ll queryMax(int v, int tl, int tr, int l, int r) {
	if (l>tr||r<tl) return -inf;
	if (l<=tl&&tr<=r) {
	    return t[v];
	} else {
	    push(v);
	    int tm=(tl+tr)/2;
	    return max(queryMax(2*v,tl,tm,l,r),queryMax(2*v+1,tm+1,tr,l,r));
	}
    }
 
    void rangeAdd(int v, int tl, int tr, int l, int r, ll dx) {
	if (l>r) return;
	if (l>tr||r<tl) return;
	if (l<=tl&&tr<=r) {
	    t[v]+=dx;
	    o[v]+=dx;
	} else {
	    push(v);
	    int tm=(tl+tr)/2;
	    rangeAdd(2*v,tl,tm,l,r,dx);
	    rangeAdd(2*v+1,tm+1,tr,l,r,dx);
	    t[v]=max(t[2*v],t[2*v+1]);
	}
    }
};

vector<int> ev[maxn];

int n, m;
vector<int> g[maxn];
int dep[maxn];
int par[maxn][LOG+1];
vector<int> leaves[maxn];
ll dp0[maxn]; // no path goes direct thru me
ll dp1[maxn]; // path goes directly thru me
vector<ll> dp[maxn]; // no path thru me, and no path thru ith leaf


void gen(int at, int p) {
    for (int j=1; j<LOG; j++) {
	par[at][j] = par[par[at][j-1]][j-1];
    }
    for (int to: g[at]) {
	if (to==p) continue;
	leaves[at].push_back(to);
	par[to][0]=at;
	dep[to]=1+dep[at];
	gen(to,at);
    }
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x,y);
    int dx=dep[x]-dep[y];
    for (int j=0; j<LOG; j++) {
	if (dx>>j&1) {
	    x=par[x][j];
	}
    }
    if (x==y) return x;

    for (int j=LOG-1; j>=0; j--) {
	if (par[x][j] != par[y][j]) {
	    x=par[x][j];
	    y=par[y][j];
	}
    }

    return par[x][0];    
}

int a[maxn], b[maxn];
ll c[maxn];
vector<int> qu[maxn];


void procQuery(int i) {
    int from = a[i];
    int to = b[i];

    int mid = lca(from, to);
    qu[mid].push_back(i);
}


void dfs(int at) {

    vector<ll> pre;
    for (int to: leaves[at]) {
	dfs(to);
	ll tmp = max(dp0[to], dp1[to]);
	pre.push_back(tmp);
	dp0[at] += tmp;
    }
    int lcount = leaves[at].size();
    for (int i=1; i<lcount; i++) {
	pre[i] += pre[i-1];
    }

    auto qry = [&](int l, int r) {
	if (l>r) return 0ll;
	return pre[r] - (l>0 ? pre[l-1] : 0ll);
    };
    
    dp[at].resize(lcount);

    // ith leaf is banned
    for (int i=0; i<lcount; i++) {
	dp[at][i] = qry(0,i-1) + qry(i+1, lcount-1);
    }


    for (int qi: qu[at]) {
	vector<vector<int>> paths;
	// get paths a->at and at<-b
	for (int nd: {a[qi],b[qi]}) {
	    if (nd==at) continue;
	    vector<int> path = {nd};
	    while (par[nd][0] != at) {
		nd=par[nd][0];
		path.push_back(nd);
	    }
	    reverse(path.begin(), path.end());
	    paths.push_back(path);
	}
	ll cur = c[qi];

	assert(int(paths.size()) <= 2);
	
	for (int to: leaves[at]) {
	    int id=-1;
	    for (int j=0; j<int(paths.size()); j++) {
		if (paths[j].front() == to) {
		    id = j;
		}
	    }

	    // at->to->...a
	    if (~id) {
		auto &p = paths[id];
		int plen = p.size();
		for (int j=0; j<plen; j++) {
		    if (j==plen-1) {
			int end = p[j];
			cur += dp0[end];
		    } else {
			int nid=0;
			while (leaves[p[j]][nid] != p[j+1]) nid++;
			cur += dp[p[j]][nid];
		    }
		}
	    } else {
		cur += max(dp0[to],dp1[to]);
	    }
	}

	dp1[at] = max(dp1[at], cur);
    }
}


ll solveTask23() {
    //cerr<<"solveTask23"<<endl;
    MaxLazySegmentTree dp;
    dp.init(n+10);
 
    auto qry = [&](int i) {
	if (i==0) return 0ll;
	return dp.queryMax(1,1,n,1,i);
    };
 
    auto upd = [&](int i, ll val) {
	ll cur = dp.queryMax(1,1,n,i,i);
	if (val <= cur) return;
	ll dx = val-cur;
	dp.rangeAdd(1,1,n,i,i,dx);
    };
 
 
    for (int i=1; i<=n; i++) {
	for (int idx: ev[i]) {
	    int l = a[idx];
	    int r = b[idx];
	    int val = c[idx];
	    upd(r, val+qry(l-1));
	}
    }
    return qry(n);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n;
    bool line = true;
    for (int i=1; i<=n-1; i++) {
	int u,v;
	cin>>u>>v;
	line &= (u==i && v==i+1);
	--u; --v;
	g[u].push_back(v);
	g[v].push_back(u);
    }

    gen(0,0);

    cin>>m;
    for (int i=0; i<m; i++) {
	cin>>a[i]>>b[i]>>c[i];
	if (line) {
	    ev[b[i]].push_back(i);
	    if (a[i]>b[i]) swap(a[i],b[i]);
	} else {
	    --a[i];
	    --b[i];
	}
	
	procQuery(i);
    }

    if (line) {
	out(solveTask23());
    }


    dfs(0);
    ll res = max(dp0[0], dp1[0]);
    cout<<res<<endl;    
    return 0;
}

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