#pragma GCC optimize("O3", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
const short MAX_N = 1e3 + 5, MAX_M = 4e3 + 5;
short n, m;
vector<short> adj[MAX_N];
struct Edge {
short u, v;
int val;
};
Edge edge[MAX_M];
short n_inds, ind[MAX_N], f_ind[MAX_N];
short depth[MAX_N];
short anc[MAX_N][11];
vector<short> children[MAX_N];
short child_ind[MAX_N];
void dfs1(short u = 1, short par = -1) {
n_inds++, ind[u] = n_inds;
for (short v : adj[u]) {
if (v == par) continue;
anc[v][0] = u, depth[v] = depth[u] + 1;
children[u].push_back(v), child_ind[v] = children[u].size() - 1;
dfs1(v, u);
}
f_ind[u] = n_inds;
}
void precomp1() {
dfs1();
for (short i = 1; i <= 10; i++)
for (short u = 1; u <= n; u++)
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
short lca(short u, short v) {
auto is_anc = [](short u, short v) { return ind[u] <= ind[v] && ind[v] <= f_ind[u]; };
if (is_anc(u, v)) return u;
if (is_anc(v, u)) return v;
for (short i = 10; i >= 0; i--)
if (anc[u][i] != 0 && !is_anc(anc[u][i], v))
u = anc[u][i];
u = anc[u][0];
return u;
}
int val_sum;
vector<short> paths[MAX_N];
void precomp2() {
for (short i = 1; i <= m; i++) {
val_sum += edge[i].val;
short w = lca(edge[i].u, edge[i].v);
short len = depth[edge[i].u] + depth[edge[i].v] - 2 * depth[w] + 1;
if (len % 2 == 0) continue;
paths[w].push_back(i);
}
}
vector<int> dp[MAX_N];
int trans[MAX_M];
void dfs2(short u = 1) {
dp[u].resize(1 << children[u].size());
for (short v : children[u]) dfs2(v);
vector<vector<short>> path_children(paths[u].size());
vector<unordered_map<short, short>> path_child(paths[u].size());
vector<vector<short>> path(paths[u].size()); // These will use the path's index in u
for (short j = 0; j < paths[u].size(); j++) {
short i = paths[u][j];
short w = lca(edge[i].u, edge[i].v);
path[j].push_back(w);
short x = edge[i].u;
while (true) {
if (x == w) break;
path[j].push_back(x);
if (anc[x][0] == w) path_children[j].push_back(x);
else path_child[j][anc[x][0]] = x;
x = anc[x][0];
}
x = edge[i].v;
while (true) {
if (x == w) break;
path[j].push_back(x);
if (anc[x][0] == w) path_children[j].push_back(x);
else path_child[j][anc[x][0]] = x;
x = anc[x][0];
}
trans[i] = edge[i].val;
for (short v : path[j]) {
if (v == u) continue;
int mask = (1 << children[v].size()) - 1;
if (path_child[j][v]) mask ^= (1 << child_ind[path_child[j][v]]);
trans[i] += dp[v][mask];
}
}
for (int mask = 0; mask <= (1 << children[u].size()) - 1; mask++) {
for (short i = 0; i <= (short) children[u].size() - 1; i++) {
if (!(mask & (1 << i))) continue;
short v = children[u][i];
dp[u][mask] += dp[v][(1 << children[v].size()) - 1];
}
for (short j = 0; j < paths[u].size(); j++) {
short i = paths[u][j];
bool halt = false;
for (short v : path_children[j])
if (!(mask & (1 << child_ind[v]))) halt = true;
if (halt) continue;
int new_mask = mask;
for (short v : path_children[j]) new_mask ^= (1 << child_ind[v]);
dp[u][mask] = max(dp[u][mask], dp[u][new_mask] + trans[i]);
}
// cout << u << " " << mask << ": " << dp[u][mask] << endl;
}
}
int main() {
// freopen("train.in", "r", stdin);
cin >> n >> m;
short new_m = 0;
for (short i = 1; i <= m; i++) {
short u, v; int val; cin >> u >> v >> val;
if (val == 0) adj[u].push_back(v), adj[v].push_back(u);
else new_m++, edge[new_m] = {u, v, val};
}
m = new_m;
precomp1();
precomp2();
dfs2();
int ans = val_sum - dp[1][(1 << children[1].size()) - 1];
cout << ans << '\n';
}
Compilation message
training.cpp: In function 'void dfs2(short int)':
training.cpp:68:25: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
68 | for (short j = 0; j < paths[u].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
training.cpp:104:29: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for (short j = 0; j < paths[u].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
10580 KB |
Output is correct |
| 2 |
Correct |
32 ms |
3676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
2 ms |
600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
860 KB |
Output is correct |
| 2 |
Correct |
4 ms |
736 KB |
Output is correct |
| 3 |
Correct |
14 ms |
2648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
12 ms |
1372 KB |
Output is correct |
| 3 |
Correct |
7 ms |
1116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
860 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2140 KB |
Output is correct |
| 3 |
Correct |
106 ms |
37392 KB |
Output is correct |
| 4 |
Correct |
20 ms |
6744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
14676 KB |
Output is correct |
| 2 |
Correct |
111 ms |
18780 KB |
Output is correct |
| 3 |
Correct |
43 ms |
10556 KB |
Output is correct |
| 4 |
Correct |
12 ms |
1116 KB |
Output is correct |
