Submission #954377

#	Time	Username	Problem	Language	Result	Execution time	Memory
954377		TAhmed33	Paths (RMI21_paths)	C++98	8 / 100	7 ms	448 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, k;
vector <pair <int, int>> adj[31];
int weight[31][31];
vector <int> cur;
void dfs (int pos, int par) {
	if (par != -1 && adj[pos].size() == 1) {
		cur.push_back(pos);
		return;
	}
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		dfs(j.first, pos);
	}
}
bool needed[31][31];
void dfs2 (int pos, int par, bool* vis, vector <pair <int, int>> &x) {
	if (vis[pos]) {
		for (auto j : x) {
			needed[j.first][j.second] = needed[j.second][j.first] = 1;
		}
	}
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		x.push_back({j.first, pos});
		dfs2(j.first, pos, vis, x);
		x.pop_back();
	}	
}
signed main () {
	cin >> n >> k;
	if (n == 1) {
		cout << "0\n";
		return 0;
	}
	for (int i = 1; i < n; i++) {
		int a, b, c; cin >> a >> b >> c;
		weight[a][b] = weight[b][a] = c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	for (int i = 1; i <= n; i++) {
		cur.clear();
		dfs(i, -1);
		int z = cur.size();
		int mx = 0;
		for (int m = 0; m < (1 << z); m++) {
			if (__builtin_popcount(m) > k) continue;
			bool marked[n + 1]; memset(marked, 0, sizeof(marked));
			for (int j = 0; j < z; j++) {
				if (m & (1 << j)) {
					marked[cur[j]] = 1;
				}
			}
			vector <pair <int, int>> cur2;
			memset(needed, 0, sizeof(needed));
			dfs2(i, -1, marked, cur2);
			int sum = 0;
			for (int j = 1; j <= n; j++) {
				for (int l = j + 1; l <= n; l++) {
					if (needed[j][l]) sum += weight[j][l];
				}
			}
			mx = max(mx, sum);
		}
		cout << mx << '\n';
	}
}	

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