This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const short MAX_N = 1e3 + 5, MAX_M = 5e3 + 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(int u = 1, int par = -1) {
n_inds++, ind[u] = n_inds;
for (int 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 (int i = 1; i <= 19; i++)
for (int u = 1; u <= n; u++)
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
int lca(int u, int v) {
auto is_anc = [](int u, int 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 (int 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], path[MAX_M];
unordered_map<short, vector<short>> path_children[MAX_M];
void precomp2() {
for (int i = 1; i <= m; i++) {
val_sum += edge[i].val;
int w = lca(edge[i].u, edge[i].v);
int len = depth[edge[i].u] + depth[edge[i].v] - 2 * depth[w] + 1;
if (len % 2 == 0) continue;
paths[w].push_back(i);
path[i].push_back(w);
auto climb = [](int u, int i, int w) {
while (true) {
if (u == w) break;
path[i].push_back(u);
path_children[i][anc[u][0]].push_back(u);
u = anc[u][0];
}
};
climb(edge[i].u, i, w), climb(edge[i].v, i, w);
}
}
int dp[MAX_N][1 << 10];
int trans[MAX_M];
void dfs2(int u = 1) {
for (int v : children[u]) dfs2(v);
for (int i : paths[u]) {
trans[i] = edge[i].val;
for (int v : path[i]) {
if (v == u) continue;
int mask = (1 << children[v].size()) - 1;
for (int w : path_children[i][v]) mask ^= (1 << child_ind[w]);
trans[i] += dp[v][mask];
}
}
for (int mask = 0; mask <= (1 << children[u].size()) - 1; mask++) {
for (int i = 0; i <= (int) children[u].size() - 1; i++) {
if (!(mask & (1 << i))) continue;
int v = children[u][i];
dp[u][mask] += dp[v][(1 << children[v].size()) - 1];
}
for (int i : paths[u]) {
bool halt = false;
for (int v : path_children[i][u])
if (!(mask & (1 << child_ind[v]))) halt = true;
if (halt) continue;
int new_mask = mask;
for (int v : path_children[i][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;
int new_m = 0;
for (int 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';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |