Submission #503706

#	Time	Username	Problem	Language	Result	Execution time	Memory
503706		atoiz	Paths (RMI21_paths)	C++14	100 / 100	181 ms	22404 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

#define len(a) ((int) ((a).size()))

struct max_k_t {
	priority_queue<int64_t, vector<int64_t>, greater<int64_t>> A, a;
	priority_queue<int64_t> B, b;
	int K;
	int64_t S;
	max_k_t(int _K = 0): A(), a(), B(), b(), K(_K), S(0) {}

	void relax() {
		while (!A.empty() && !a.empty() && A.top() == a.top()) A.pop(), a.pop();
		while (!B.empty() && !b.empty() && B.top() == b.top()) B.pop(), b.pop();
	}

	void add(int64_t x) {
		if (len(A) - len(a) < K) {
			A.push(x), S += x;
		} else if (A.top() >= x) {
			B.push(x);
		} else {
			B.push(A.top());
			S -= A.top(), A.pop();
			A.push(x), S += x;
		}
		relax();
	}

	void del(int64_t x) {
		if (B.empty() || B.top() >= x) {
			b.push(x);
		} else {
			a.push(x); S -= x;

			if (!B.empty()) {
				A.push(B.top()), S += B.top();
				B.pop();
			}
		}
		relax();
	}
};

const int MAXN = 100007;
int N, K;
int64_t up[MAXN], down[MAXN], ans[MAXN];
max_k_t max_k;
vector<pair<int, int>> G[MAXN];

void dfs_down(int u, int p) {
	for (auto [w, v] : G[u]) if (v != p) {
		dfs_down(v, u);
		down[u] = max(down[u], down[v] + w);
	}
}

void dfs_up(int u, int p) {
	vector<pair<int64_t, int>> vec;
	for (auto [w, v] : G[u]) if (v != p) vec.emplace_back(down[v] + w, v);
	if (len(vec) >= 2) {
		for (int i = 0; i < 2; ++i) swap(vec[i], *max_element(vec.begin() + i, vec.end()));
		for (int i = 1; i < len(vec); ++i) max_k.add(vec[i].first);
		vec.resize(2);
	}

	for (auto [w, v] : G[u]) if (v != p) {
		up[v] = up[u] + w;
		for (auto [x, y] : vec) if (y != v) {
			up[v] = max(up[v], x + w);
		}
		dfs_up(v, u);
	}
}

void dfs_ans(int u, int p) {
	ans[u] = max_k.S;
	for (auto [w, v] : G[u]) if (v != p) {
		max_k.add(down[v]), max_k.add(up[v]);
		max_k.del(down[v] + w), max_k.del(up[v] - w);
		dfs_ans(v, u);
		max_k.add(down[v] + w), max_k.add(up[v] - w);
		max_k.del(down[v]), max_k.del(up[v]);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> K;
	for (int i = 0; i < N - 1; ++i) {
		int u, v, w; cin >> u >> v >> w;
		G[u].emplace_back(w, v);
		G[v].emplace_back(w, u);
	}
	max_k = max_k_t(K);
	dfs_down(1, 0), dfs_up(1, 0);
	max_k.add(down[1]);
	if (len(G[1]) == 1) max_k.add(0);
	dfs_ans(1, 0);
	for (int u = 1; u <= N; ++u) cout << ans[u] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'void dfs_down(int, int)':
Main.cpp:58:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |  for (auto [w, v] : G[u]) if (v != p) {
      |            ^
Main.cpp: In function 'void dfs_up(int, int)':
Main.cpp:66:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |  for (auto [w, v] : G[u]) if (v != p) vec.emplace_back(down[v] + w, v);
      |            ^
Main.cpp:73:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |  for (auto [w, v] : G[u]) if (v != p) {
      |            ^
Main.cpp:75:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |   for (auto [x, y] : vec) if (y != v) {
      |             ^
Main.cpp: In function 'void dfs_ans(int, int)':
Main.cpp:84:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |  for (auto [w, v] : G[u]) if (v != p) {
      |            ^

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