Submission #871087

#	Time	Username	Problem	Language	Result	Execution time	Memory
871087		MinaRagy06	Paths (RMI21_paths)	C++17	36 / 100	1067 ms	11344 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define md ((l + r) >> 1)

pair<ll, int> seg[1 << 18];
void build(int i, int l, int r) {
	if (l == r) {
		seg[i] = {-1e18, l};
		return;
	}
	build(i << 1, l, md);
	build(i << 1 | 1, md + 1, r);
	seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}
void upd(int i, int l, int r, int x, int t, ll v) {
	if (l == x && x == r) {
		if (t == 0) {
			seg[i].first += v;
		} else {
			seg[i].first = v;
		}
		return;
	}
	if (x <= md) {
		upd(i << 1, l, md, x, t, v);
	} else {
		upd(i << 1 | 1, md + 1, r, x, t, v);
	}
	seg[i] = max(seg[i << 1], seg[i << 1 | 1]);
}
pair<ll, int> get(int i, int l, int r, int s, int e) {
	if (s <= l && r <= e) {
		return seg[i];
	}
	if (r < s || e < l) {
		return {-1e18, l};
	}
	return max(get(i << 1, l, md, s, e), get(i << 1 | 1, md + 1, r, s, e));
}
const int N = 100'005;
vector<array<int, 2>> adj[N];
int n, k, st[N], en[N], t;
void dfs(int i, int par, int parc) {
	st[i] = t++;
	for (auto [nxt, w] : adj[i]) {
		if (nxt == par) continue;
		dfs(nxt, i, w);
	}
	en[i] = t;
	if (adj[i].size() == 1) {
		upd(1, 1, n, st[i], 1, 0);
	}
	pair<ll, int> val = get(1, 1, n, st[i], en[i]);
	upd(1, 1, n, val.second, 0, parc);
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> k;
	for (int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for (int i = 1; i <= n; i++) {
		build(1, 1, n);
		t = 1;
		dfs(i, 0, 0);
		ll sum = 0;
		int cnt = k;
		while (cnt--) {
			pair<ll, int> val = get(1, 1, n, 1, n);
			sum += val.first;
			upd(1, 1, n, val.second, 1, -1e18);
		}
		cout << sum << '\n';
	}
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 11 / 11
• Subtask 3: 17 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 12
• Subtask 6: 0 / 32