Submission #755325

#	Time	Username	Problem	Language	Result	Execution time	Memory
755325		jmyszka2007	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	284 ms	41332 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pi pair<int, int>
#define pb push_back
struct sc {
	int s1, s2, val, a, b;
};
constexpr int LIM = 1e5;
constexpr int base = (1 << 17);
vector<int>g[LIM + 10];
int pre[LIM + 10];
int post[LIM + 10];
int nxt[LIM + 10][18];
ll dp[LIM + 10][2];
vector<sc>zap[LIM + 10];
ll tri[2 * base][2];
int ojhld[LIM + 10];
int siz[LIM + 10];
bool czy(int a, int b) {
	return pre[a] <= pre[b] && post[a] >= post[b];
}
pair<int, pi> lca(int a, int b) {
	if(pre[a] <= pre[b]) {
		swap(a, b);
	}
	for(int i = 17; i >= 0; i--) {
		if(!czy(nxt[a][i], b)) {
			a = nxt[a][i];
		}
	}
	if(nxt[a][0] == b) {
		return {nxt[a][0], {a, 0}};
	}
	for(int i = 17; i >= 0; i--) {
		if(!czy(nxt[b][i], a)) {
			b = nxt[b][i];
		}
	}
	return {nxt[a][0], {a, b}};	
}
void prepare(int v, int o) {
	siz[v] = 1;
	int mx = 0;
	for(auto x : g[v]) {
		if(x != o) {
			prepare(x, v);
			siz[v] += siz[x];
			mx = max(mx, siz[x]);
		}
	}
	for(int i = 0; i < g[v].size(); i++) {
		if(g[v][i] != o && siz[g[v][i]] == mx) {
			swap(g[v][i], g[v][0]);
		}
	}
}
int aktpre = 1, aktpost = 1;
void dfs(int v, int o) {
	pre[v] = aktpre++;
	nxt[v][0] = o;
	for(int i = 1; i <= 17; i++) {
		nxt[v][i] = nxt[nxt[v][i - 1]][i - 1];
	}
	for(int i = 0; i < g[v].size(); i++) {
		if(g[v][i] != o) {
			if(i) {
				ojhld[g[v][i]] = g[v][i];
			}
			else {
				ojhld[g[v][i]] = ojhld[v];
			}
			dfs(g[v][i], v);
		}
	}
	post[v] = aktpost++;
}
void upd(int v, ll x, int k) {
	v += base;
	tri[v][k] = x;
	v /= 2;
	while(v > 0) {
		tri[v][k] = tri[2 * v][k] + tri[2 * v + 1][k];
		v /= 2;
	}
}
ll que(int l, int r, int k) {
	l += base;
	r += base;
	ll ans = 0;
	while(l <= r) {
		if(l & 1) {
			ans += tri[l][k];
		}
		if(!(r & 1)) {
			ans += tri[r][k];
		}
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
ll hld(int a, int b, int k) {
	//cout << "\nHLD " << a << ' ' << b << ' ' << k << '\n';
	ll ans = 0;
	while(pre[a] >= pre[b]) {
		if(pre[ojhld[a]] <= pre[b]) {
			//cout << a << ' ' << b << ' ' << que(pre[b], pre[a], k) << '\n';
			ans += que(pre[b], pre[a], k);
			break;
		}
		else {
			//cout << a << ' ' << ojhld[a] << ' ' << que(pre[ojhld[a]], pre[a], k) << '\n';;
			ans += que(pre[ojhld[a]], pre[a], k);
			a = nxt[ojhld[a]][0];
		}
	}
	//cout << "KONIEC\n";
	return ans;
}
void cntdp(int v, int o) {
	int sum = 0;
	for(auto x : g[v]) {
		if(x != o) {
			cntdp(x, v);
			sum += max(dp[x][0], dp[x][1]);
		}
	}
	dp[v][0] = sum;
	upd(pre[v], dp[v][0], 0);
	for(auto x : zap[v]) {
		if(x.b == v) {
			//cout << x.a << ' ' << x.b << ' ' << v << ' ' << x.val << ' ' <<  hld(x.a, v, 0) << ' ' << hld(x.a, x.s1, 1) << '\n';
			dp[v][1] = max(dp[v][1], hld(x.a, v, 0) - hld(x.a, x.s1, 1) + x.val);
		}
		else {
			//cout << v << ' ' << x.a << ' ' << x.b << ' ' << x.val << ' ' << hld(x.a, v, 0) << ' ' << hld(x.a, x.s1, 1)  << ' '  << hld(x.b, x.s2, 1) << '\n';
			dp[v][1] = max(dp[v][1], hld(x.a, v, 0) - hld(x.a, x.s1, 1) + hld(x.b, x.s2, 0) - hld(x.b, x.s2, 1) + x.val);
		}
	}
	//cout << v << ' ' << dp[v][0] << ' ' << dp[v][1] << '\n';
	upd(pre[v], max(dp[v][0], dp[v][1]), 1);
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for(int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	prepare(1, 1);	
	ojhld[1] = 1;
	dfs(1, 1);
	int t;
	cin >> t;
	for(int i = 1; i <= t; i++) {
		int a, b, x;
		cin >> a >> b >> x;
		pair<int, pi> tmp = lca(a, b);
		sc tmp2;
		if(pre[a] <= pre[b]) {
			swap(a, b);
		}
		tmp2.a = a;
		tmp2.b = b;
		tmp2.val = x;
		tmp2.s1 = tmp.nd.st;
		tmp2.s2 = tmp.nd.nd;
		zap[tmp.st].pb(tmp2);
	}
	cntdp(1, 1);
	cout << max(dp[1][0], dp[1][1]) << '\n';
}

Compilation message (stderr)

election_campaign.cpp: In function 'void prepare(int, int)':
election_campaign.cpp:54:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i = 0; i < g[v].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
election_campaign.cpp: In function 'void dfs(int, int)':
election_campaign.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |  for(int i = 0; i < g[v].size(); i++) {
      |                 ~~^~~~~~~~~~~~~

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