Submission #1224395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224395		pakapu	Paths (RMI21_paths)	C++20	19 / 100	1098 ms	97832 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n, k;
int ans = 0;
vector<int> leaves;
vector<int> sum_left;
vector<vector<pair<int, int>>> g;
vector<vector<pair<int, int>>> path;

void get_leaves(int u, int prev)
{
	bool is_leaf = true;
	for (auto &v : g[u]) {
		if (v.first == prev) {
			continue;
		}
		is_leaf = false;
		get_leaves(v.first, u);
	}

	if (is_leaf) {
		leaves.push_back(u);
	}
}

void get_paths(int u, int prev)
{
	for (auto &v : g[u]) {
		if (v.first == prev) {
			continue;
		}

		path[v.first] = path[u];
		path[v.first].push_back({u, v.second});
		sum_left[v.first] = sum_left[u] + v.second;
		get_paths(v.first, u);
	}
}

void dfs(int u, int prev)
{
	for (auto &v : g[u]) {
		if (v.first == prev) {
			continue;
		}
	}
}

int solve_for_root(int root)
{
	int curr = 0;
	vector<vector<pair<int, int>>> g_backup = g;

	for (int i = 0; i < k; i++) {
		sum_left = vector<int>(n);
		path = vector<vector<pair<int, int>>>(n);
		get_paths(root, -1);
		int mx = max_element(sum_left.begin(), sum_left.end()) - sum_left.begin();
		int prev = mx;

		//cout << mx << " :  ";
		reverse(path[mx].begin(), path[mx].end());
		for (auto &v : path[mx]) {
			curr += v.second;
			(*find(g[v.first].begin(), g[v.first].end(), make_pair(prev, v.second))).second = 0;
			(*find(g[prev].begin(), g[prev].end(), make_pair(v.first, v.second))).second = 0;
			//cout << "(" << v.first << ", " << v.second << ") ";
			prev = v.first;
		}
		// cout << '\n';
		// for (int i = 0; i < n; i++) {
		// 	cout << "I = " << i << " :  ";
		// 	for (auto &c : g[i]) {
		// 		cout << "(" << c.first << ", " << c.second << ") ";
		// 	}
		// 	cout << '\n';
		// }
		// for (auto &c : sum_left) {
		// 	cout << c << ' ';
		// }
		// cout << '\n';
	}

	g = g_backup;

	return curr;
}

void solve()
{
	cin >> n >> k;

	g = vector<vector<pair<int, int>>>(n);

	for (int i = 1; i < n; i++) {
		int from, to, treats;
		cin >> from >> to >> treats;
		from--;
		to--;
		g[from].push_back({to, treats});
		g[to].push_back({from, treats});
	}

	for (int i = 0; i < n; i++) {
		cout << solve_for_root(i) << '\n';
	}
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int tt = 1;
	//cin >> tt;

	while (tt--) {
		solve();
	}

	return 0;
}

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