#include <bits/stdc++.h>
using namespace std;
struct Edge
{
unsigned u, v, w;
};
vector<vector<unsigned>> g, anc;
vector<unsigned> height, ind;
vector<vector<Edge>> unpaved;
vector<vector<unsigned>> dp;
unsigned lift(unsigned u, unsigned h)
{
unsigned z = 0;
while (h)
{
if (h & 1)
{
assert(z < anc[u].size());
u = anc[u][z];
}
h >>= 1;
z++;
}
return u;
}
unsigned lca(unsigned u, unsigned v)
{
assert(u < g.size() && v < g.size());
if (height[u] < height[v])
swap(u, v);
u = lift(u, height[u] - height[v]);
if (u == v)
return u;
for (unsigned i = anc[u].size() - 1; i < anc[u].size(); i--)
{
if (anc[u][i] != anc[v][i])
{
u = anc[u][i];
v = anc[v][i];
}
}
return anc[u][0];
}
void traverse(unsigned u, vector<unsigned> &path, unsigned p = -1, unsigned h = 0)
{
for (unsigned i = 1; i <= path.size(); i <<= 1)
anc[u].push_back(path[path.size() - i]);
height[u] = h;
path.push_back(u);
for (unsigned const &v : g[u])
if (v != p)
traverse(v, path, u, h + 1);
for (auto it = g[u].begin(); it != g[u].end(); it++)
{
if (*it == p)
{
g[u].erase(it);
break;
}
}
path.pop_back();
}
void calc_dp(unsigned u)
{
for (unsigned const &v : g[u])
{
calc_dp(v);
}
dp[u] = vector<unsigned>(1 << g[u].size());
// Case 1. Just delete the root and add up subtree values.
for (unsigned z = 0; z < 1U << g[u].size(); z++)
{
dp[u][z] = 0;
for (unsigned i = 0; i < g[u].size(); i++)
{
if (!(z & (1 << i)))
{
assert(g[u][i] < g.size());
dp[u][z] += dp[g[u][i]][0];
}
}
}
for (unsigned i = 0; i < g[u].size(); i++)
{
ind[g[u][i]] = i;
}
// Case 2: Take exactly one unpaved road whose tree path contains u.
for (auto const &[a, b, w] : unpaved[u])
{
// Stores just the value obtained from the two used subtrees.
unsigned x = 0;
if (a != u)
{
x += dp[a][0];
unsigned r = a, s = anc[a][0];
while (s != u)
{
assert(1 << ind[r] < dp[s].size());
x += dp[s][1 << ind[r]];
r = s;
s = anc[s][0];
}
}
if (b != u)
{
x += dp[b][0];
unsigned r = b, s = anc[b][0];
while (s != u)
{
x += dp[s][1 << ind[r]];
r = s;
s = anc[s][0];
}
}
unsigned p = UINT_MAX, q = UINT_MAX;
if (a != u)
p = ind[lift(a, height[a] - height[u] - 1)];
if (b != u)
q = ind[lift(b, height[b] - height[u] - 1)];
for (unsigned z = 0; z < 1U << g[u].size(); z++)
{
if ((a != u && (z & (1 << p))) || (b != u && (z & (1 << q))))
continue;
unsigned y = 0;
// Sum all children not on an edge path and not ruled out.
for (unsigned i = 0; i < g[u].size(); i++)
{
if (!(z & (1 << i)) && i != p && i != q)
{
y += dp[g[u][i]][0];
}
}
dp[u][z] = max(dp[u][z], x + y + w);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t n, m;
cin >> n >> m;
g = vector<vector<unsigned>>(n);
vector<Edge> unpaved_edges;
unsigned total_cost = 0;
for (size_t i = 0; i < m; i++)
{
unsigned u, v, w;
cin >> u >> v >> w;
total_cost += w;
if (!w)
{
g[u - 1].push_back(v - 1);
g[v - 1].push_back(u - 1);
}
else
{
unpaved_edges.push_back({u - 1, v - 1, w});
}
}
height = vector<unsigned>(n);
anc = vector<vector<unsigned>>(n);
vector<unsigned> path;
traverse(0, path);
unpaved = vector<vector<Edge>>(n);
for (auto const &[u, v, w] : unpaved_edges)
{
if (!((height[u] + height[v]) & 1))
{
unpaved[lca(u, v)].push_back({u, v, w});
}
}
dp = vector<vector<unsigned>>(n);
ind = vector<unsigned>(n);
calc_dp(0);
cout << total_cost - dp[0][0] << '\n';
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from training.cpp:1:
training.cpp: In function 'void calc_dp(unsigned int)':
training.cpp:112:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<unsigned int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | assert(1 << ind[r] < dp[s].size());
| ~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
980 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1108 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1208 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
