#include <bits/stdc++.h>
#define pb push_back
using namespace std;
constexpr static int SIZE = 1000;
constexpr static int LOG_SIZE = 11;
constexpr static int SUBTREE_SIZE = 11;
vector<int> g[SIZE];
vector<array<int, 3>> lower_children[SIZE];
int dp[SIZE][SUBTREE_SIZE][SIZE+1]; // current_node, closed subtree (open if 10), last_blocking (if equal to n it means no blocking
int best[SIZE][SUBTREE_SIZE][SIZE][SUBTREE_SIZE]; // Highest cost connection from subtree to subtree (given subtree is closed)
int depth[SIZE];
vector<array<int, 3>> edges;
int mapping[SIZE];
int n;
struct LCA
{
int bl[SIZE][LOG_SIZE];
void construct()
{
for (int i = 1; i < LOG_SIZE; i++)
for (int j = 0; j < n; j++)
bl[j][i] = bl[bl[j][i-1]][i-1];
}
int advance(int node, int k)
{
for (int i = 0; i < LOG_SIZE; i++)
if ((1<<i)&k)
node = bl[node][i];
return node;
}
void equalize_depths(int& a, int& b)
{
if (depth[a] > depth[b])
a = advance(a, depth[a]-depth[b]);
else if (depth[b] > depth[a])
b = advance(b, depth[b]-depth[a]);
}
array<int, 2> get_subtree_pair(int a, int b)
{
equalize_depths(a, b);
for (int i = LOG_SIZE-1; i >= 0; i--)
if (bl[a][i] != bl[b][i])
a = bl[a][i], b = bl[b][i];
return array<int,2>({a,b});
}
int get(int a, int b)
{
equalize_depths(a, b);
if (a == b)
return a;
else
return bl[get_subtree_pair(a, b)[0]][0];
}
int parent(int node)
{
return bl[node][0];
}
};
LCA lca;
int sort_children(int node, int parent);
void dfs1(int node, int parent)
{
if (parent == -1)
{
depth[node] = 0;
lca.bl[node][0] = node;
}
else
{
depth[node] = depth[parent] + 1;
lca.bl[node][0] = parent;
}
for (int c : g[node])
if (c != parent)
dfs1(c, node);
sort_children(node, parent);
}
int get_proper_subtree(int node, int subtree)
{
int parent = lca.parent(subtree);
if (depth[node] == depth[subtree])
return -1;
int below = lca.advance(node, depth[node] - depth[subtree] - 1);
return mapping[below];
}
// O(n)
void process_edges()
{
for (auto [a, b, c] : edges)
{
if ((depth[a]+depth[b])&1)
continue;
if (depth[a] > depth[b])
swap(a, b);
if (lca.get(a, b) == a)
{
int proper_subtree = mapping[lca.advance(b, depth[b] - depth[a] - 1)];
lower_children[a].pb({a, c, proper_subtree});
}
else
{
auto [ast, bst] = lca.get_subtree_pair(a, b);
int apst = get_proper_subtree(a, ast), bpst = get_proper_subtree(b, bst);
for (int i = 0; i < SUBTREE_SIZE; i++)
for (int j = 0; j < SUBTREE_SIZE; j++)
if (i != apst && j != bpst)
best[ast][i][bst][j] = max(best[ast][i][bst][j], c);
}
}
}
int sort_children(int node, int parent)
{
for (int i = 0; i < g[node].size(); i++)
{
if (g[node][i] == parent)
{
swap(g[node].back(), g[node][i]);
break;
}
}
int last = g[node].size();
if (parent != -1)
last--;
sort(g[node].begin(), g[node].begin() + last);
for (int i = 0; i < last; i++)
mapping[g[node][i]] = i;
return last;
}
void dfs2(int node, int parent)
{
for (int c : g[node])
if (c != parent)
dfs2(c, node);
sort_children(node, parent);
int last = sort_children(node, parent);
vector<vector<int>> best_pairs(last, vector<int>(last));
for (int i = 0; i < last; i++)
{
for (int j = 0; j < SUBTREE_SIZE; j++)
{
best_pairs[i][i] = max(best_pairs[i][i], dp[g[node][i]][j][n]);
for (int k = i+1; k < last; k++)
{
for (int l = 0; l < SUBTREE_SIZE; l++)
{
int val = dp[g[node][i]][j][n] + dp[g[node][k]][l][n] + best[g[node][i]][j][g[node][k]][l];
best_pairs[i][k] = max(best_pairs[i][k], val);
}
}
}
}
vector<int> pdp(1<<last);
for (int i = 0; i < pdp.size(); i++)
for (int j = 0; j < last; j++)
for (int k = j; k < last; k++)
if (!(i&(1<<j)) && !(i&(1<<k)))
pdp[i|(1<<j)|(1<<k)] = max(pdp[i|(i<<j)|(1<<k)], pdp[i] + best_pairs[j][k]);
for (int i = 0; i < n; i++)
if (i != node)
for (int j = 0; j < last; j++)
dp[node][SUBTREE_SIZE-1][i] = max(dp[node][SUBTREE_SIZE-1][i], dp[g[node][j]][SUBTREE_SIZE-1][i] + pdp[((1<<last)-1)^(1<<j)]);
dp[node][SUBTREE_SIZE-1][n] = max(dp[node][SUBTREE_SIZE-1][n], pdp[(1<<last)-1]);
for (auto [lc, c, pst] : lower_children[node])
for (int i = 0; i < last; i++)
dp[node][pst][n] = max(dp[node][pst][n], pdp[((1<<last)-1)^(1<<i)] + dp[g[node][i]][SUBTREE_SIZE-1][lc] + c);
for (int i = 0; i < SUBTREE_SIZE; i++)
dp[node][i][node] = dp[node][i][n];
}
int main()
{
int m;
cin >> n >> m;
int total_cost = 0;
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
a--, b--;
if (c == 0)
{
g[a].pb(b);
g[b].pb(a);
}
else
{
edges.pb({a, b, c});
total_cost += c;
}
}
dfs1(0, -1);
lca.construct();
process_edges();
dfs2(0, -1);
int reduction = 0;
for (int i = 0; i < SUBTREE_SIZE; i++)
reduction = max(reduction, dp[0][i][0]);
cout << (total_cost - reduction) << "\n";
}
Compilation message
training.cpp: In function 'int get_proper_subtree(int, int)':
training.cpp:87:13: warning: unused variable 'parent' [-Wunused-variable]
87 | int parent = lca.parent(subtree);
| ^~~~~~
training.cpp: In function 'int sort_children(int, int)':
training.cpp:122:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < g[node].size(); i++)
| ~~^~~~~~~~~~~~~~~~
training.cpp: In function 'void dfs2(int, int)':
training.cpp:163:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for (int i = 0; i < pdp.size(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
2516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
43764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
3476 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
12520 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
18408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
40220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
62684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
19368 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
43 ms |
30444 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
