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;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> g(n);
vector<array<int, 3>> e;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
--u; --v;
if (w == 0) {
g[u].push_back(v);
g[v].push_back(u);
} else {
e.push_back({u, v, w});
}
}
const int L = 20;
vector<vector<int>> jump(n, vector<int>(L));
vector<int> dep(n);
function<void(int, int)> Dfs = [&](int v, int pv) {
jump[v][0] = pv;
for (int i = 1; i < L; i++) {
jump[v][i] = jump[jump[v][i - 1]][i - 1];
}
for (int u : g[v]) {
if (u == pv) {
continue;
}
dep[u] = dep[v] + 1;
Dfs(u, v);
}
};
auto LCA = [&](int u, int v) {
if (dep[u] > dep[v]) {
swap(u, v);
}
for (int i = L - 1; i >= 0; i--) {
if (dep[jump[v][i]] >= dep[u]) {
v = jump[v][i];
}
}
if (u == v) {
return u;
}
for (int i = L - 1; i >= 0; i--) {
if (jump[u][i] != jump[v][i]) {
u = jump[u][i];
v = jump[v][i];
}
}
return jump[u][0];
};
auto GetDist = [&](int u, int v) {
return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
};
Dfs(0, 0);
long long s = 0;
vector<vector<array<int, 3>>> qs(n);
for (auto &p : e) {
s += p[2];
if (GetDist(p[0], p[1]) % 2 == 1) {
continue;
}
qs[LCA(p[0], p[1])].push_back(p);
}
vector<vector<long long>> dp(n);
vector<int> idx(n);
vector<int> deg(n);
Dfs = [&](int v, int pv) {
long long sum_ch = 0;
vector<int> ch;
for (int i = 0; i < (int) g[v].size(); i++) {
int u = g[v][i];
if (u == pv) {
continue;
}
deg[v] += 1;
Dfs(u, v);
sum_ch += *max_element(dp[u].begin(), dp[u].end());
idx[u] = (int) ch.size();
ch.push_back(u);
}
dp[v].resize(1 << deg[v]);
fill(dp[v].begin(), dp[v].end(), 0LL);
for (int mask = 0; mask < (1 << deg[v]); mask++) {
for (int i = 0; i < deg[v]; i++) {
if (mask >> i & 1) {
dp[v][mask] += *max_element(dp[ch[i]].begin(), dp[ch[i]].end());
}
}
}
vector<pair<int, long long>> opt;
for (auto &p : qs[v]) {
int a = p[0];
int b = p[1];
int c = p[2];
long long ft = c + sum_ch;
int mask = 0;
{
int x = a;
int prv = -1;
while (x != v) {
int cmask = (1 << deg[x]) - 1;
if (prv != -1) {
cmask ^= (1 << idx[prv]);
}
ft += dp[x][cmask];
prv = x;
x = jump[x][0];
}
if (prv != -1) {
mask ^= (1 << idx[prv]);
ft -= *max_element(dp[prv].begin(), dp[prv].end());
}
}
{
int x = b;
int prv = -1;
while (x != v) {
int cmask = (1 << deg[x]) - 1;
if (prv != -1) {
cmask ^= (1 << idx[prv]);
}
ft += dp[x][cmask];
prv = x;
x = jump[x][0];
}
if (prv != -1) {
mask ^= (1 << idx[prv]);
ft -= *max_element(dp[prv].begin(), dp[prv].end());
}
}
opt.push_back({mask, ft});
}
for (auto &p : opt) {
auto new_dp = dp[v];
for (int mask = 0; mask < (1 << deg[v]); mask++) {
if (mask & p.first) {
continue;
}
new_dp[mask | p.first] = max(new_dp[mask | p.first], dp[v][mask] + p.second);
}
swap(dp[v], new_dp);
}
};
Dfs(0, 0);
cout << s - dp[0].back() << '\n';
return 0;
}
# | 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... |