답안 #531089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531089	2022-02-27T18:01:43 Z	blue	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	1000 ms	134084 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

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	50380 KB	Output is correct
2	Incorrect	29 ms	50380 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	50356 KB	Output is correct
2	Correct	26 ms	50380 KB	Output is correct
3	Correct	24 ms	50972 KB	Output is correct
4	Correct	351 ms	132852 KB	Output is correct
5	Correct	363 ms	133940 KB	Output is correct
6	Correct	358 ms	134008 KB	Output is correct
7	Correct	337 ms	133896 KB	Output is correct
8	Correct	390 ms	133936 KB	Output is correct
9	Correct	321 ms	133956 KB	Output is correct
10	Correct	350 ms	133836 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	24 ms	50356 KB	Output is correct
2	Correct	26 ms	50380 KB	Output is correct
3	Correct	24 ms	50972 KB	Output is correct
4	Correct	351 ms	132852 KB	Output is correct
5	Correct	363 ms	133940 KB	Output is correct
6	Correct	358 ms	134008 KB	Output is correct
7	Correct	337 ms	133896 KB	Output is correct
8	Correct	390 ms	133936 KB	Output is correct
9	Correct	321 ms	133956 KB	Output is correct
10	Correct	350 ms	133836 KB	Output is correct
11	Correct	36 ms	51596 KB	Output is correct
12	Correct	348 ms	133876 KB	Output is correct
13	Correct	344 ms	133944 KB	Output is correct
14	Correct	343 ms	134008 KB	Output is correct
15	Correct	340 ms	133876 KB	Output is correct
16	Correct	335 ms	134012 KB	Output is correct
17	Correct	364 ms	133888 KB	Output is correct
18	Correct	372 ms	133956 KB	Output is correct
19	Correct	342 ms	134084 KB	Output is correct
20	Correct	348 ms	133852 KB	Output is correct