Submission #71026

#	Time	Username	Problem	Language	Result	Execution time	Memory
71026		MatheusLealV	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	281 ms	31104 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];

int solve(int x, int f)
{
	if(dp[x][f] != -1) return dp[x][f];

	dp[x][f] = 0;

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

		dp[x][f] += solve(v, 0);
	}

	if(f) return dp[x][f];

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

		int ans = c + (a != x ? solve(a, 1) : 0) + (b != x ? solve(b, 1) : 0);

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

			if(ini[v] <= ini[a] and ini[a] <= fim[v]) continue;

			if(ini[v] <= ini[b] and ini[b] <= fim[v]) continue;

			ans += solve(v, 0);
		}

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

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

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