Submission #531057

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531057	2022-02-27T14:11:40 Z	blue	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	276 ms	126984 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];
	}

	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	30 ms	50432 KB	Output is correct
2	Correct	29 ms	50432 KB	Output is correct
3	Incorrect	26 ms	50452 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	50436 KB	Output is correct
2	Correct	26 ms	50432 KB	Output is correct
3	Correct	26 ms	50960 KB	Output is correct
4	Correct	232 ms	126612 KB	Output is correct
5	Correct	274 ms	126608 KB	Output is correct
6	Correct	219 ms	126640 KB	Output is correct
7	Correct	276 ms	126652 KB	Output is correct
8	Correct	263 ms	126592 KB	Output is correct
9	Correct	239 ms	126644 KB	Output is correct
10	Correct	259 ms	126672 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	50436 KB	Output is correct
2	Correct	26 ms	50432 KB	Output is correct
3	Correct	26 ms	50960 KB	Output is correct
4	Correct	232 ms	126612 KB	Output is correct
5	Correct	274 ms	126608 KB	Output is correct
6	Correct	219 ms	126640 KB	Output is correct
7	Correct	276 ms	126652 KB	Output is correct
8	Correct	263 ms	126592 KB	Output is correct
9	Correct	239 ms	126644 KB	Output is correct
10	Correct	259 ms	126672 KB	Output is correct
11	Correct	37 ms	51472 KB	Output is correct
12	Correct	237 ms	126896 KB	Output is correct
13	Correct	212 ms	126912 KB	Output is correct
14	Correct	197 ms	126984 KB	Output is correct
15	Correct	211 ms	126872 KB	Output is correct
16	Correct	197 ms	126904 KB	Output is correct
17	Correct	208 ms	126912 KB	Output is correct
18	Correct	207 ms	126916 KB	Output is correct
19	Correct	189 ms	126932 KB	Output is correct
20	Correct	206 ms	126844 KB	Output is correct