oj.uz

Submission #531088

# Submission time Handle Problem Language Result Execution time Memory
531088 2022-02-27T17:58:49 Z blue Election Campaign (JOI15_election_campaign) C++17
20 / 100
 1000 ms 129596 KB 
#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);
	
		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';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 50440 KB Output is correct
2 Correct 24 ms 50400 KB Output is correct
3 Correct 25 ms 50404 KB Output is correct
4 Correct 26 ms 50636 KB Output is correct
5 Correct 171 ms 73888 KB Output is correct
6 Correct 163 ms 129596 KB Output is correct
7 Correct 561 ms 108080 KB Output is correct
8 Correct 88 ms 71576 KB Output is correct
9 Correct 583 ms 104444 KB Output is correct
10 Correct 96 ms 71620 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 50368 KB Output is correct
2 Correct 26 ms 50428 KB Output is correct
3 Correct 29 ms 50952 KB Output is correct
4 Execution timed out 1059 ms 129192 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 50368 KB Output is correct
2 Correct 26 ms 50428 KB Output is correct
3 Correct 29 ms 50952 KB Output is correct
4 Execution timed out 1059 ms 129192 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1052 ms 76508 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 50440 KB Output is correct
2 Correct 24 ms 50400 KB Output is correct
3 Correct 25 ms 50404 KB Output is correct
4 Correct 26 ms 50636 KB Output is correct
5 Correct 171 ms 73888 KB Output is correct
6 Correct 163 ms 129596 KB Output is correct
7 Correct 561 ms 108080 KB Output is correct
8 Correct 88 ms 71576 KB Output is correct
9 Correct 583 ms 104444 KB Output is correct
10 Correct 96 ms 71620 KB Output is correct
11 Correct 33 ms 50700 KB Output is correct
12 Correct 32 ms 50940 KB Output is correct
13 Correct 30 ms 50884 KB Output is correct
14 Correct 28 ms 50600 KB Output is correct
15 Correct 30 ms 50640 KB Output is correct
16 Correct 31 ms 50752 KB Output is correct
17 Correct 28 ms 50636 KB Output is correct
18 Correct 40 ms 50852 KB Output is correct
19 Correct 28 ms 50584 KB Output is correct
20 Correct 29 ms 51008 KB Output is correct

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 50440 KB Output is correct
2 Correct 24 ms 50400 KB Output is correct
3 Correct 25 ms 50404 KB Output is correct
4 Correct 26 ms 50636 KB Output is correct
5 Correct 171 ms 73888 KB Output is correct
6 Correct 163 ms 129596 KB Output is correct
7 Correct 561 ms 108080 KB Output is correct
8 Correct 88 ms 71576 KB Output is correct
9 Correct 583 ms 104444 KB Output is correct
10 Correct 96 ms 71620 KB Output is correct
11 Correct 24 ms 50368 KB Output is correct
12 Correct 26 ms 50428 KB Output is correct
13 Correct 29 ms 50952 KB Output is correct
14 Execution timed out 1059 ms 129192 KB Time limit exceeded
15 Halted 0 ms 0 KB -