Submission #531058

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531058	2022-02-27T14:16:56 Z	blue	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	303 ms	133700 KB

election_campaign

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

const int mx = 100'000;
const int lg = 17;

int N, M;

vi edge[1 + mx];


int anc[1 + mx][1 + lg];
vi desc[1 + mx][1 + lg];
int depth[1 + mx];

void dfs0(int u)
{
	// cerr << "dfs0 " << u << '\n';
	for(int v : edge[u])
	{
		// cerr << "considering " << v << '\n';
		if(anc[u][0] == v) continue;
		// cerr << u << " -> " << v << '\n';
		anc[v][0] = u;
		desc[u][0].push_back(v);
		depth[v] = 1 + depth[u];
		dfs0(v);
	}
	// cerr << "u done\n";
}

int ancestor(int u, int k)
{
	for(int e = 0; e <= lg; e++)
		if(k & (1 << e))
			u = anc[u][e];
	return u;
}

pii prelca(int u, int v)
{
	if(depth[u] > depth[v]) swap(u, v);
	v = ancestor(v, depth[v] - depth[u]);

	if(u == v) return {u, v};

	for(int e = lg; e >= 0; e--)
	{
		if(anc[u][e] == anc[v][e]) continue;
		u = anc[u][e];
		v = anc[v][e];
	}

	return {u, v};
}







struct route
{
	int a;
	int b;
	int c;

	int aa;
	int ab;
};

vector<pii> vert[1 + mx];
vector<route> horiz[1 + mx];

vi DP(1 + mx, 0);

int DPsum[1 + mx][1 + lg];

vi childsum(1 + mx, 0);




int chainsum(int u, int d)
{
	int res = 0;

	for(int e = lg; e >= 0; e--)
	{
		if(d & (1 << e))
		{
			res += DPsum[u][e];
			u = anc[u][e];
		}
	}

	return res;
}

void blift(int u, int e)
{
	if(e == 0)
	{
		DPsum[u][e] = childsum[anc[u][0]] - DP[u];
	}
	else
	{
		DPsum[u][e] = DPsum[u][e-1] + DPsum[ anc[u][e-1] ][e-1];
	}

	for(int v : desc[u][e-1])
	{
		blift(v, e-1);
	}
}


void dfs(int u)
{
	for(int v : desc[u][0])
	{
		dfs(v);
		childsum[u] += DP[v];
	}

	for(int v : desc[u][0])
	{
		blift(v, 0);
	}

	DP[u] = childsum[u];

	for(pii vr : vert[u])
	{
		// cerr << "vr : " << u << " -> " << vr.first << '\n';
		// int rightchild = ancestor(vr.first, depth[vr.first] - depth[u] - 1);
		DP[u] = max(DP[u], childsum[u] - DP[ancestor(vr.first, depth[vr.first] - depth[u] - 1)] + chainsum(vr.first, depth[vr.first] - depth[u]) + childsum[vr.first] + vr.second);
	}

	for(route hr : horiz[u])
	{
		DP[u] = max(DP[u], chainsum(hr.a, depth[hr.a] - depth[u] - 1) + childsum[hr.a]
			             + chainsum(hr.b, depth[hr.b] - depth[u] - 1) + childsum[hr.b]
			             + childsum[u] - DP[hr.aa] - DP[hr.ab]
			             + hr.c);
	}
}








int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	for(int e = 1; e <= N-1; e++)
	{
		int u, v;
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}


	for(int i = 0; i <= N; i++)
		for(int e = 0; e <= lg; e++)
			anc[i][e] = 0;

	depth[1] = 1;

	dfs0(1);

	for(int e = 1; e <= lg; e++)
	{
		for(int u = 0; u <= N; u++)
		{
			// cerr << u << ' ' << e << " ! \n";
			anc[u][e] = anc[ anc[u][e-1] ][e-1];

			if(anc[u][e] != 0) 
				desc[ anc[u][e] ][e].push_back(u);
		}
	}

	// cerr << "A\n";


	cin >> M;

	for(int j = 1; j <= M; j++)
	{
		route r;
		cin >> r.a >> r.b >> r.c;

		if(depth[r.a] > depth[r.b]) swap(r.a, r.b);

		pii pl = prelca(r.a, r.b);
		r.aa = pl.first, r.ab = pl.second;

		if(pl.first == pl.second) vert[pl.first].push_back({r.a + r.b - pl.first, r.c});
		else
		{
			horiz[ anc[pl.first][0] ].push_back(r);
		}
	}


	dfs(1);


	cout << DP[1] << '\n';
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	50380 KB	Output is correct
2	Incorrect	26 ms	50380 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	50380 KB	Output is correct
2	Correct	25 ms	50380 KB	Output is correct
3	Correct	27 ms	51000 KB	Output is correct
4	Correct	217 ms	133700 KB	Output is correct
5	Correct	223 ms	133656 KB	Output is correct
6	Correct	233 ms	133656 KB	Output is correct
7	Correct	234 ms	133672 KB	Output is correct
8	Correct	259 ms	133700 KB	Output is correct
9	Correct	202 ms	131276 KB	Output is correct
10	Correct	235 ms	131252 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	50380 KB	Output is correct
2	Correct	25 ms	50380 KB	Output is correct
3	Correct	27 ms	51000 KB	Output is correct
4	Correct	217 ms	133700 KB	Output is correct
5	Correct	223 ms	133656 KB	Output is correct
6	Correct	233 ms	133656 KB	Output is correct
7	Correct	234 ms	133672 KB	Output is correct
8	Correct	259 ms	133700 KB	Output is correct
9	Correct	202 ms	131276 KB	Output is correct
10	Correct	235 ms	131252 KB	Output is correct
11	Correct	36 ms	51276 KB	Output is correct
12	Correct	221 ms	131152 KB	Output is correct
13	Correct	242 ms	131176 KB	Output is correct
14	Correct	281 ms	131316 KB	Output is correct
15	Correct	232 ms	131168 KB	Output is correct
16	Correct	204 ms	131276 KB	Output is correct
17	Correct	303 ms	131140 KB	Output is correct
18	Correct	216 ms	131164 KB	Output is correct
19	Correct	214 ms	131288 KB	Output is correct
20	Correct	239 ms	131180 KB	Output is correct