oj.uz

Submission #497550

# Submission time Handle Problem Language Result Execution time Memory
497550 2021-12-23T09:02:03 Z zhougz Roadside Advertisements (NOI17_roadsideadverts) C++17
30 / 100
 92 ms 13076 KB 
/**
 *    author: zhougz
 *    created: 23/12/2021 16:33:58
**/
#include <bits/stdc++.h>

using namespace std;

int n, k;
const int MAXN = 50'050, MAXK = log2(MAXN) + 1;
vector<pair<int, int>> v[MAXN];
int anc[MAXN][MAXK], dist[MAXN][MAXK], dep[MAXN];

void dfs(int x, int par, int w, int d) {
	anc[x][0] = par;
	dist[x][0] = w;
	dep[x] = d;
	for (int i = 1; i <= k; i++) {
		int half_par = anc[x][i - 1];
		if (half_par == -1) {
			break;
		}
		anc[x][i] = anc[half_par][i - 1];
		dist[x][i] = dist[x][i - 1] + dist[half_par][i - 1];
	}
	for (const auto &[z, w] : v[x]) {
		if (z != par) {
			dfs(z, x, w, d + 1);
		}
	}
}

int get_lca(int a, int b) {
	if (dep[a] > dep[b]) {
		swap(a, b);
	}
	int cur_dist = 0;
	int extra = dep[b] - dep[a];
	for (int i = 0; i <= k; i++) {
		if (extra & (1 << i)) {
			cur_dist += dist[b][i];
			b = anc[b][i];
		}
	}
	if (a == b) { // a was already the parent
		return cur_dist;
		//return make_pair(a, cur_dist);
	}
	for (int i = k; i >= 0; i--) {
		if (anc[a][i] == anc[b][i]) {
			continue;
		}
		cur_dist += dist[a][i] + dist[b][i];
		a = anc[a][i];
		b = anc[b][i];
	}
	assert(a != b && anc[a][0] == anc[b][0]);
	return cur_dist + dist[a][0] + dist[b][0];
	//return make_pair(anc[a][0], cur_dist + dist[a][0] + dist[b][0]);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(anc, -1, sizeof anc);
	cin >> n;
	k = log2(n - 1);
	for (int i = 0, a, b, w; i < n - 1; i++) {
		cin >> a >> b >> w;
		v[a].emplace_back(b, w);
		v[b].emplace_back(a, w);
	}
	dfs(0, -1, 0, 0);
	int q;
	cin >> q;
	for (int i = 0, arr[5]; i < q; i++) {
		for (int j = 0; j < 5; j++) {
			cin >> arr[j];
		}
		sort(arr, arr + 5, [&](int a, int b) {
			return dep[a] < dep[b];
		});
		int res = 0;
		for (int j = 1; j < 5; j++) {
			int bst = INT_MAX;
			for (int k = 0; k < j; k++) {
				bst = min(bst, get_lca(arr[k], arr[j]));
			}
			res += bst;
		}
		cout << res << '\n';
	}
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 11844 KB Output is correct
2 Correct 82 ms 12960 KB Output is correct
3 Correct 55 ms 12964 KB Output is correct
4 Correct 73 ms 13076 KB Output is correct
5 Correct 62 ms 12964 KB Output is correct
6 Correct 76 ms 12856 KB Output is correct
7 Correct 66 ms 12852 KB Output is correct
8 Correct 67 ms 12924 KB Output is correct
9 Correct 92 ms 12944 KB Output is correct
10 Correct 65 ms 12976 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 10524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4564 KB Output is correct
2 Correct 74 ms 11844 KB Output is correct
3 Correct 82 ms 12960 KB Output is correct
4 Correct 55 ms 12964 KB Output is correct
5 Correct 73 ms 13076 KB Output is correct
6 Correct 62 ms 12964 KB Output is correct
7 Correct 76 ms 12856 KB Output is correct
8 Correct 66 ms 12852 KB Output is correct
9 Correct 67 ms 12924 KB Output is correct
10 Correct 92 ms 12944 KB Output is correct
11 Correct 65 ms 12976 KB Output is correct
12 Incorrect 30 ms 10524 KB Output isn't correct
13 Halted 0 ms 0 KB -