Submission #531093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
531093	2022-02-27T18:03:57 Z	blue	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	1000 ms	132908 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];
	}

	if(e <= lg)
	{
		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:149:7: warning: unused variable 'rightchild' [-Wunused-variable]
  149 |   int rightchild = ancestor(vr.first, depth[vr.first] - depth[u] - 1);
      |       ^~~~~~~~~~

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	50380 KB	Output is correct
2	Incorrect	25 ms	50372 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	24 ms	50360 KB	Output is correct
2	Correct	24 ms	50380 KB	Output is correct
3	Correct	25 ms	51004 KB	Output is correct
4	Correct	345 ms	132740 KB	Output is correct
5	Correct	351 ms	132800 KB	Output is correct
6	Correct	327 ms	132804 KB	Output is correct
7	Correct	357 ms	132816 KB	Output is correct
8	Correct	340 ms	132728 KB	Output is correct
9	Correct	337 ms	132820 KB	Output is correct
10	Correct	343 ms	132712 KB	Output is correct

Subtask #3
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	50360 KB	Output is correct
2	Correct	24 ms	50380 KB	Output is correct
3	Correct	25 ms	51004 KB	Output is correct
4	Correct	345 ms	132740 KB	Output is correct
5	Correct	351 ms	132800 KB	Output is correct
6	Correct	327 ms	132804 KB	Output is correct
7	Correct	357 ms	132816 KB	Output is correct
8	Correct	340 ms	132728 KB	Output is correct
9	Correct	337 ms	132820 KB	Output is correct
10	Correct	343 ms	132712 KB	Output is correct
11	Correct	34 ms	51276 KB	Output is correct
12	Correct	344 ms	132696 KB	Output is correct
13	Correct	363 ms	132760 KB	Output is correct
14	Correct	326 ms	132868 KB	Output is correct
15	Correct	348 ms	132864 KB	Output is correct
16	Correct	348 ms	132792 KB	Output is correct
17	Correct	354 ms	132704 KB	Output is correct
18	Correct	348 ms	132804 KB	Output is correct
19	Correct	333 ms	132884 KB	Output is correct
20	Correct	381 ms	132908 KB	Output is correct