Submission #71039

#	Time	Username	Problem	Language	Result	Execution time	Memory
71039		MatheusLealV	Election Campaign (JOI15_election_campaign)	C++17	20 / 100	1092 ms	32436 KiB

election_campaign

#include <bits/stdc++.h>
#define N 100050
#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;

vector<int> grafo[N];

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], best[N][logn], opt[N][logn][2] ;

inline void update(int x)
{
	best[x][0] = max({dp[x][0], dp[x][1], dp[anc[x][0]][0], dp[anc[x][0]][1]});

	opt[x][0][0] = max(dp[x][0], dp[anc[x][0]][1]);

	opt[x][0][1] = max(dp[x][1], dp[anc[x][0]][1]);

	for(int j = 1; j < logn; j++)
	{
		if(anc[x][j - 1] == -1) continue;

		best[x][j] = max(best[anc[x][j - 1]][j - 1], best[x][j - 1]);

		opt[x][j][0] = max(opt[anc[x][j - 1]][j - 1][0], opt[x][j - 1][0]);

		opt[x][j][1] = max(opt[anc[x][j - 1]][j - 1][1], opt[x][j - 1][1]);
	}
}

int solve(int x, int f)
{
	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 nivel = deep[x], u = a;

			int somamax = 0, soma1 = 0, soma0 = 0;

			while(u != x)
			{
				soma1 += dp[u][1];

				soma0 += dp[u][0];

				somamax += max(dp[u][1], dp[u][0]); 

				u = anc[u][0];
			}

			u = b;

			while(u != x)
			{
				soma1 += dp[u][1];

				soma0 += dp[u][0];

				somamax += max(dp[u][1], dp[u][0]); 

				u = anc[u][0];
			}

			int ans = soma + c - somamax + soma1;

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

	//update(x);

	return dp[x][f];
}

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

	cin>>n;

	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";
}

Compilation message (stderr)

election_campaign.cpp: In function 'int solve(int, int)':
election_campaign.cpp:93:8: warning: unused variable 'nivel' [-Wunused-variable]
    int nivel = deep[x], u = a;
        ^~~~~

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