Submission #380511

#	Time	Username	Problem	Language	Result	Execution time	Memory
380511		pure_mem	Election Campaign (JOI15_election_campaign)	C++14	0 / 100	219 ms	22820 KiB

election_campaign

#include <bits/stdc++.h>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 12;
const ll INF = 1e18;

int n, q, lca[17][N], T, timer, tin[N], tout[N];
ll dp[N], sp[N], fw[2][N];
vector< int > g[N];
vector< pair< pair<int, int>, int > > ask[N];

void upd(int v, ll val){
	for(;v <= timer;v |= v + 1)
		fw[T][v] += val;
}
ll get(int v){
	ll res = 0;
	for(;v >= 0;v = (v & (v + 1)) - 1)
		res += fw[T][v];
	return res;
}
void dfs(int v, int pr){
	lca[0][v] = pr;	
	tin[v] = ++timer;
	for(int to: g[v]){
		if(to != pr){
			dfs(to, v);
		}
	}
	tout[v] = ++timer;
}
bool check(int x, int y){
	if(tin[x] <= tin[y] && tout[y] <= tout[x])
		return 1;
	return 0;
}
int get_pr(int x, int y){
	if(check(x, y)) 	
		return x;
	else if(check(y, x))
		return y;
	for(int i = 16;i >= 0;i--){
		if(!check(lca[i][x], y))
			x = lca[i][x];
	}
	return lca[0][x];
}
void dfs2(int v, int pr){
	for(int to: g[v]){
		if(to != pr){
			dfs2(to, v);
			sp[v] += dp[to];
		}
	}
	dp[v] = sp[v]; 
	T = 0, upd(tin[v], sp[v]), upd(tout[v], -sp[v]);
	for(pair< pair<int, int>, int > tmp: ask[v]){
		int x = tmp.X.X, y = tmp.X.Y;
		ll cur = tmp.Y;
		T = 0, cur += get(tin[x]) + get(tin[y]) - 2 * get(tin[v]) + sp[v];
		T = 1;
		if(x != v)
			cur -= get(tin[lca[0][x]]) - get(tin[v]);
		if(y != v)
			cur -= get(tin[lca[0][y]]) - get(tin[v]);
		dp[v] = max(dp[v], cur);
	}
	T = 1, upd(tin[v], dp[v]), upd(tout[v], -dp[v]); 
}

int main () {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1, x, y;i < n;i++){
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1, 1);
	for(int i = 1;i < 17;i++){
		for(int j = 1;j <= n;j++){
			lca[i][j] = lca[i - 1][lca[i - 1][j]];
		}
	}
	cin >> q; 
	for(int i = 1, x, y, z;i <= q;i++){
		cin >> x >> y >> z;
		int v = get_pr(x, y);
		ask[v].push_back(MP(MP(x, y), z));
	}	
	dfs2(1, 1);
	cout << dp[1];
}

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