Submission #395570

#	Time	Username	Problem	Language	Result	Execution time	Memory
395570		arwaeystoamneg	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	407 ms	57488 KiB

election_campaign

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
const int MAX = 100005, SZ = 20;
int n, m, depth[MAX];
vi adj[MAX];
vector<pair<pii, int>>queries[MAX];
ll a[MAX], dp[MAX];
template<int SZ>struct hld
{
	struct item
	{
		ll sum;
	};
	item single(ll i)
	{
		return { i };
	}
	item merge(item x, item y)
	{
		item ans;
		ans.sum = x.sum + y.sum;
		return ans;
	}
	vector<item> tree;
	vector<item>A;
	int height;
	item neutral = { 0 };
	void build(vector<item>& A, int v, int tl, int tr)
	{
		if (tl == tr)
			tree[v] = A[tl];
		else
		{
			int mid = (tl + tr) / 2;
			build(A, 2 * v + 1, tl, mid);
			build(A, 2 * v + 2, mid + 1, tr);
			tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		}
	}
	void build(vll& B)
	{
		int	n = B.size();
		height = log2(n + 1) + 1;
		A.rsz(n);
		tree.rsz((1 << height + 1) - 1);
		F0R(i, n)A[i] = single(B[i]);
		A.rsz(1 << height, neutral);
		build(A, 0, 0, (1 << height) - 1);
	}
	item query(int v, int tl, int tr, int l, int r)
	{
		if (r<tl || l>tr)return neutral;
		if (l <= tl && r >= tr)
		{
			return tree[v];
		}
		int mid = (tl + tr) / 2;
		return merge(query(2 * v + 1, tl, mid, l, r), query(2 * v + 2, mid + 1, tr, l, r));
	}
	ll query(int l, int r)
	{
		return query(0, 0, (1 << height) - 1, l, r).sum;
	}
	void update(int v, int tl, int tr, int pos, item val)
	{
		if (tl == tr)
		{
			tree[v] = val;
		}
		else
		{
			int mid = (tl + tr) / 2;
			if (pos <= mid)
				update(2 * v + 1, tl, mid, pos, val);
			else
				update(2 * v + 2, mid + 1, tr, pos, val);
			tree[v] = merge(tree[2 * v + 1], tree[2 * v + 2]);
		}
	}
	void update(int pos, ll val)
	{
		update(0, 0, (1 << height) - 1, pos, single(val));
	}
	vi label, sizes, depth, heavy_child, parent, head, dist;
	vector<vi>jump;
	int get(int a, int b)
	{
		F0R(j, SZ)
		{
			if (b & (1 << j))
			{
				a = jump[a][j];
			}
		}
		return a;
	}
	int LCA(int a, int b)
	{
		if (depth[a] < depth[b])swap(a, b);
		a = get(a, depth[a] - depth[b]);
		if (a == b)return a;
		int j = SZ;
		while (j)
		{
			j--;
			int ta = jump[a][j], tb = jump[b][j];
			if (ta != tb)a = ta, b = tb;
		}
		return parent[a];
	}
	void dfs0(int i, int p)
	{
		parent[i] = p;
		sizes[i] = 1;
		trav(x, adj[i])
		{
			if (x == p)continue;
			depth[x] = depth[i] + 1;
			dfs0(x, i);
			sizes[i] += sizes[x];
		}
	}
	int cur = 0;
	void dfs1(int i, int p)
	{
		label[i] = cur++;
		if (heavy_child[i] != -1)
		{
			head[heavy_child[i]] = head[i];
			dfs1(heavy_child[i], i);
			dist[i] = 1 + dist[heavy_child[i]];
		}
		trav(x, adj[i])
		{
			if (x != heavy_child[i] && x != p)
			{
				head[x] = x;
				dfs1(x, i);
			}
		}
	}
	void init()
	{
		sizes.rsz(n);
		depth.rsz(n);
		parent.rsz(n);
		dfs0(0, -1);
		jump.rsz(n, vi(SZ));
		F0R(i, n)jump[i][0] = parent[i];
		F0R(i, SZ - 1)
		{
			F0R(j, n)jump[j][i + 1] = (jump[j][i] == -1 ? -1 : jump[jump[j][i]][i]);
		}
		heavy_child.rsz(n);
		F0R(i, n)
		{
			vpi t;
			trav(x, adj[i])if (parent[i] != x)t.pb({ sizes[x],x });
			sort(all(t), greater<pii>());
			if (sz(t))heavy_child[i] = t[0].s;
			else heavy_child[i] = -1;
		}
		label.rsz(n);
		head.rsz(n);
		dist.rsz(n);
		dfs1(0, -1);
		vll t(n);
		F0R(i, n)t[label[i]] = a[i];
		build(t);
	}
	ll solve(int x, int l)// find the sum of the values from x to l excluding l.
	{
		ll ans = 0;
		while (1)
		{
			if (x == l)return ans;
			if (head[x] == x)
			{
				ans += a[x];
				x = parent[x];
				continue;
			}
			int h = head[x];
			if (depth[h] > depth[l])
			{
				ans += query(label[h], label[x]);
				x = parent[h];
				continue;
			}
			ans += query(label[l] + 1, label[x]);
			x = l;
		}
		return ans;
	}
	ll query_path(int x, int y)
	{
		int l = LCA(x, y);
		return solve(x, l) + solve(y, l) + a[l];
	}
	void update_path(int x, int y)
	{
		a[x] = y;
		update(label[x], y);
	}
};

hld<SZ>g;
void dfs(int i, int p = -1)
{
	ll sum = 0;
	trav(x, adj[i])
	{
		if (x == p)continue;
		depth[x] = depth[i] + 1;
		dfs(x, i);
		dp[i] = max(dp[i], dp[x]);
		sum += dp[x];
	}
	trav(x, queries[i])
	{
		int l = i;
		ll val = 0;
		if (l == x.f.f)swap(x.f.f, x.f.s);
		if (l == x.f.s)
		{
			val = g.query_path(g.get(x.f.f, depth[x.f.f] - depth[l] - 1), x.f.f) + x.s + sum;
		}
		else
		{
			val = g.query_path(g.get(x.f.f, depth[x.f.f] - depth[l] - 1), x.f.f) + g.query_path(x.f.s, g.get(x.f.s, depth[x.f.s] - depth[l] - 1)) + x.s + sum;
		}
		dp[i] = max(dp[i], val);
	}
	trav(x, adj[i])
	{
		if (x == p)continue;
		a[i] += dp[x];
	}
	a[i] -= dp[i];
	g.update_path(i, a[i]);
}
int main() 
{
	setIO("test1");
	cin >> n;
	F0R(i, n - 1)
	{
		int x, y;
		cin >> x >> y;
		adj[--x].pb(--y);
		adj[y].pb(x);
	}
	g.init();
	cin >> m;
	F0R(i, m)
	{
		int x, y, z;
		cin >> x >> y >> z;
		int l = g.LCA(--x, --y);
		queries[l].pb({ {x,y},z });
	}
	dfs(0);
	cout << dp[0] << endl;
}

Compilation message (stderr)

election_campaign.cpp: In instantiation of 'void hld<SZ>::build(vll&) [with int SZ = 20; vll = std::vector<long long int>]':
election_campaign.cpp:221:3:   required from 'void hld<SZ>::init() [with int SZ = 20]'
election_campaign.cpp:305:9:   required from here
election_campaign.cpp:97:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   97 |   tree.rsz((1 << height + 1) - 1);
      |                  ~~~~~~~^~~

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