Submission #520859

#	Time	Username	Problem	Language	Result	Execution time	Memory
520859		ymm	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	198 ms	66860 KiB

election_campaign

///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 100010;
vector<int> A[N];
int st[N], ft[N], rt[N];
vector<pair<int,pii>> C[N];
int n, m;

namespace rmq
{
	const int lg = 20;
	vector<pii> vec;
	pii a[lg][2*N];
	int n;

	void init(){
		n = vec.size();
		Loop(i,0,n) a[0][i] = vec[i];
		Loop(k,0,lg-1) for(int i=0; i+(2<<k)<=n; ++i)
			a[k+1][i] = min(a[k][i], a[k][i+(1<<k)]);
	}

	pii get(int l, int r){
		int k = __lg(r-l);
		return min(a[k][l], a[k][r-(1<<k)]);
	}
}

void dfs1(int v, int p, int h, int& t){
	st[v] = t++;
	rt[v] = rmq::vec.size();
	rmq::vec.emplace_back(h, v);
	for(int u : A[v])
		if(u != p)
			dfs1(u, v, h+1, t),
			rmq::vec.emplace_back(h, v);
	ft[v] = t;
}

mt19937 rd(time(0));
struct node
{
	node *l=0, *r=0;
	int key, val, lzy=0;
	int pri=rd();
	node(int x, int y){key=x;val=y;}
};

void ppg(node* t){
	if(t->lzy){
		t->val += t->lzy;
		if(t->l) t->l->lzy += t->lzy;
		if(t->r) t->r->lzy += t->lzy;
		t->lzy = 0;
	}
}

int get(node* t, int k){
	assert(t);
	ppg(t);
	if(k < t->key) return get(t->l, k);
	if(k > t->key) return get(t->r, k);
	return t->val;
}

node* merge(node* t, node* u){
	if(!t) return u;
	if(!u) return t;
	if(t->pri > u->pri){
		ppg(t);
		t->r = merge(t->r, u);
		return t;
	} else {
		ppg(u);
		u->l = merge(t, u->l);
		return u;
	}
}

pair<int,node*> dfs2(int v, int p){
	vector<int> st, cv;
	vector<node*> ct;
	int csum=0;
	for(int u : A[v]){
		if(u==p) continue;
		st.push_back(::st[u]);
		auto [x, y] = dfs2(u, v);
		csum += x;
		cv.push_back(x);
		ct.push_back(y);
	}
	int ans = csum;
	for(auto [w, pr] : C[v]){
		auto [a, b] = pr;
		int ca = upper_bound(st.begin(), st.end(), ::st[a])-st.begin()-1;
		int cb = upper_bound(st.begin(), st.end(), ::st[b])-st.begin()-1;
		int val = csum + w;
		if(ca>=0) val += get(ct[ca], ::st[a])-cv[ca];
		if(cb>=0) val += get(ct[cb], ::st[b])-cv[cb];
		ans = max(ans, val);
	}
	node* t = new node(::st[v], csum);
	Loop(i,0,ct.size()){
		ct[i]->lzy += csum-cv[i];
		t = merge(t, ct[i]);
	}
	return {ans, t};
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n;
	Loop(i,1,n){
		int v, u;
		cin >> v >> u;
		--v; --u;
		A[v].push_back(u);
		A[u].push_back(v);
	}
	dfs1(0, -1, 0, *new int(0));
	rmq::init();
	cin >> m;
	Loop(i,0,m){
		int a, b, x;
		cin >> a >> b >> x;
		--a; --b;
		if(rt[a] > rt[b]) swap(a, b);
		int lca = rmq::get(rt[a], rt[b]+1).second;
		C[lca].push_back({x, {a, b}});
	}
	cout << dfs2(0, -1).first << '\n';
}

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