Submission #71052

#	Time	Username	Problem	Language	Result	Execution time	Memory
71052		MatheusLealV	Election Campaign (JOI15_election_campaign)	C++17	100 / 100	662 ms	40028 KiB

election_campaign

#include <bits/stdc++.h>
#define N 100050
#define l (2*nod)
#define r (2*nod + 1)
#define mid ((a + b)/2)
#define logn 20
using namespace std;

struct qr{
	int a, b, c;
};

vector<qr> Q[N];

int n, q, anc[N][logn], deep[N], ini[N], fim[N], t;

struct T
{
	int tree[4*N], lazy[4*N];

	void clear()
	{
		memset(tree, 0, sizeof tree);

		memset(lazy, 0, sizeof lazy);
	}

	inline void prop(int nod, int a, int b)
	{
		if(!lazy[nod]) return;

		tree[nod] += (b - a + 1)*lazy[nod];

		if(a != b)
		{
			lazy[l] += lazy[nod];

			lazy[r] += lazy[nod];
		}

		lazy[nod] = 0;
	}

	void upd(int nod, int a, int b, int i, int j, int x)
	{
		prop(nod, a, b);

		if(j < a or i > b) return;

		if(i <= a and j >= b)
		{
			tree[nod] += (b - a + 1)*x;

			if(a != b)
			{
				lazy[l] += x;

				lazy[r] += x;
			}

			return;
		}

		upd(l, a, mid, i, j, x), upd(r, mid + 1, b, i, j, x);

		tree[nod] = tree[l] + tree[r];
	}

	int query(int nod, int a, int b, int i, int j)
	{
		prop(nod, a, b);

		if(j < a or i > b) return 0;

		if(i <= a and j >= b) return tree[nod];

		return query(l, a, mid, i, j) + query(r, mid + 1, b, i, j);
	}

} Tree[2];

vector<int> grafo[N];

inline int LCA(int u, int v)
{
	if(deep[u] < deep[v]) swap(u, v);

	for(int i = logn - 1; i >= 0; i--)
		if(deep[u] - (1<<i) >= deep[v]) u = anc[u][i];

	if(u == v) return u;

	for(int i = logn - 1; i >= 0; i--)
		if(anc[u][i] != -1 and anc[v][i] != -1 and anc[u][i] != anc[v][i])
			u = anc[u][i], v = anc[v][i];

	return anc[u][0];
}

void dfs(int x, int p)
{
	anc[x][0] = p;

	ini[x] = ++t;

	for(auto v: grafo[x])
	{
		if(v == p) continue;

		deep[v] = deep[x] + 1;

		dfs(v, x);
	}

	fim[x] = t;
}

int dp[N][2], ok[N][2];

int solve(int x, int f)
{
	ok[x][f] = 1;

	if(dp[x][f] != -1) return dp[x][f];

	int soma = 0;

	for(auto v: grafo[x])
	{
		if(v == anc[x][0]) continue;

		soma += max(solve(v, 1), solve(v, 0));
	}

	dp[x][f] = soma;

	if(!f)
	{
		for(auto q: Q[x])
		{
			int a = q.a, b = q.b, c = q.c;

			int A = Tree[0].query(1, 1, n, ini[x], ini[x]);

			int B = Tree[1].query(1, 1, n, ini[x], ini[x]);

			int somamax = Tree[0].query(1, 1, n, ini[a], ini[a]) - A;

			int soma1 = Tree[1].query(1, 1, n, ini[a], ini[a]) - B;

			somamax += Tree[0].query(1, 1, n, ini[b], ini[b]) - A;

			soma1 += Tree[1].query(1, 1, n, ini[b], ini[b]) - B;

			int ans = soma + c - somamax + soma1;

			dp[x][f] = max(dp[x][f], ans);
		}
	}

	if(f) Tree[1].upd(1, 1, n, ini[x], fim[x], dp[x][1]);

	else Tree[0].upd(1, 1, n, ini[x], fim[x], max(dp[x][0], dp[x][1]));

	return dp[x][f];
}

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

	cin>>n;

	Tree[0].clear(), Tree[1].clear();

	for(int i = 1, a, b; i < n; i++)
	{
		cin>>a>>b;

		grafo[a].push_back(b);

		grafo[b].push_back(a);
	}

	memset(anc, -1, sizeof anc);

	dfs(1, 1);

	for(int j = 1; j < logn; j++)
		for(int i = 1; i <= n; i++) anc[i][j] = anc[anc[i][j - 1]][j - 1];

	cin>>q;

	for(int i = 1, a, b, c; i <= q; i++)
	{
		cin>>a>>b>>c;

		int L = LCA(a, b);

		Q[L].push_back({a, b, c});
	}

	memset(dp, -1, sizeof dp);

	cout<<solve(1, 0)<<"\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