Submission #531090

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531090	2022-02-27T18:02:04 Z	blue	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	379 ms	129864 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])
	{
		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);
	
		// vi good(1 + N, 0);

		// for(int k = vr.first; 1; k = anc[k][0])
		// {
		// 	good[k] = 1;
		// 	if(k == u) break;
		// }

		// int cr = vr.second;

		// for(int i = 1; i <= N; i++)
		// 	for(int j : desc[i][0])
		// 		if(good[i] && !good[j]) cr += DP[j];

		// DP[u] = max(DP[u], cr);
	}

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

		// vi good(1 + N, 0);

		// for(int k = hr.a; 1; k = anc[k][0])
		// {
		// 	good[k] = 1;
		// 	if(k == u) break;
		// }
		// for(int k = hr.b; 1; k = anc[k][0])
		// {
		// 	good[k] = 1;
		// 	if(k == u) break;
		// }

		// int cr = hr.c;

		// for(int i = 1; i <= N; i++)
		// 	for(int j : desc[i][0])
		// 		if(good[i] && !good[j]) cr += DP[j];

		// DP[u] = max(DP[u], cr);

		// cerr << childsum[u] << ' ' << DP[hr.aa] << ' ' << DP[hr.ab] << '\n';
	}
}








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

Compilation message

election_campaign.cpp: In function 'void dfs(int)':
election_campaign.cpp:145:7: warning: unused variable 'rightchild' [-Wunused-variable]
  145 |   int rightchild = ancestor(vr.first, depth[vr.first] - depth[u] - 1);
      |       ^~~~~~~~~~

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	50380 KB	Output is correct
2	Incorrect	28 ms	50424 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	23 ms	50340 KB	Output is correct
2	Correct	28 ms	50380 KB	Output is correct
3	Correct	27 ms	50884 KB	Output is correct
4	Correct	376 ms	129572 KB	Output is correct
5	Correct	350 ms	129668 KB	Output is correct
6	Correct	358 ms	129792 KB	Output is correct
7	Correct	337 ms	129652 KB	Output is correct
8	Correct	373 ms	129588 KB	Output is correct
9	Correct	316 ms	129688 KB	Output is correct
10	Correct	355 ms	129584 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	50340 KB	Output is correct
2	Correct	28 ms	50380 KB	Output is correct
3	Correct	27 ms	50884 KB	Output is correct
4	Correct	376 ms	129572 KB	Output is correct
5	Correct	350 ms	129668 KB	Output is correct
6	Correct	358 ms	129792 KB	Output is correct
7	Correct	337 ms	129652 KB	Output is correct
8	Correct	373 ms	129588 KB	Output is correct
9	Correct	316 ms	129688 KB	Output is correct
10	Correct	355 ms	129584 KB	Output is correct
11	Correct	34 ms	51240 KB	Output is correct
12	Correct	354 ms	129620 KB	Output is correct
13	Correct	365 ms	129624 KB	Output is correct
14	Correct	352 ms	129628 KB	Output is correct
15	Correct	356 ms	129864 KB	Output is correct
16	Correct	335 ms	129624 KB	Output is correct
17	Correct	379 ms	129764 KB	Output is correct
18	Correct	353 ms	129608 KB	Output is correct
19	Correct	332 ms	129792 KB	Output is correct
20	Correct	347 ms	129732 KB	Output is correct