oj.uz

Submission #954377

# Submission time Handle Problem Language Result Execution time Memory
954377 2024-03-27T17:54:56 Z TAhmed33 Paths (RMI21_paths) C++
8 / 100
 7 ms 448 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 3 ms 448 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Runtime error 1 ms 436 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Runtime error 1 ms 436 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Runtime error 1 ms 436 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 348 KB Output is correct
2 Correct 3 ms 448 KB Output is correct
3 Runtime error 1 ms 436 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -