#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][20];
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 <= 19; 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 = 19; 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);
}
}
int dp[MAX_N][1 << 10];
int trans[MAX_M];
void dfs2(short u = 1) {
for (short v : children[u]) dfs2(v);
vector<unordered_map<short, vector<short>>> path_children(paths[u].size());
vector<vector<int>> 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];
int w = lca(edge[i].u, edge[i].v);
path[j].push_back(w);
int x = edge[i].u;
while (true) {
if (x == w) break;
path[j].push_back(x);
path_children[j][anc[x][0]].push_back(x);
x = anc[x][0];
}
x = edge[i].v;
while (true) {
if (x == w) break;
path[j].push_back(x);
path_children[j][anc[x][0]].push_back(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;
for (short w : path_children[j][v]) mask ^= (1 << child_ind[w]);
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][u])
if (!(mask & (1 << child_ind[v]))) halt = true;
if (halt) continue;
int new_mask = mask;
for (short v : path_children[j][u]) new_mask ^= (1 << child_ind[v]);
dp[u][mask] = max(dp[u][mask], dp[u][new_mask] + trans[i]);
}
}
}
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:66:25: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for (short j = 0; j < paths[u].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~
training.cpp:100:29: warning: comparison of integer expressions of different signedness: 'short int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | 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 |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
25092 KB |
Output is correct |
| 2 |
Correct |
47 ms |
10688 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 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 |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
604 KB |
Output is correct |
| 2 |
Correct |
0 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
860 KB |
Output is correct |
| 2 |
Correct |
2 ms |
860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1624 KB |
Output is correct |
| 2 |
Correct |
5 ms |
3164 KB |
Output is correct |
| 3 |
Correct |
29 ms |
6048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
28 ms |
2384 KB |
Output is correct |
| 3 |
Correct |
10 ms |
2140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
1368 KB |
Output is correct |
| 2 |
Correct |
15 ms |
4700 KB |
Output is correct |
| 3 |
Correct |
264 ms |
80372 KB |
Output is correct |
| 4 |
Correct |
37 ms |
14232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
30548 KB |
Output is correct |
| 2 |
Correct |
202 ms |
42092 KB |
Output is correct |
| 3 |
Correct |
70 ms |
23180 KB |
Output is correct |
| 4 |
Correct |
27 ms |
2396 KB |
Output is correct |
