Submission #696633

#TimeUsernameProblemLanguageResultExecution timeMemory
696633vjudge1Training (IOI07_training)C++17
100 / 100
17 ms20552 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; typedef pair <int, int> pii; typedef pair <ll, ll> pll; #define fir first #define sec second typedef vector <int> vi; typedef vector <ll> vl; template <typename __Tp> void read(__Tp &x) { int f = 0; x = 0; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1; for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48); if (f) x = -x; } template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &...y) { read(x), read(y...); } template <typename __Tp> void write(__Tp x) { if (x < 0) putchar('-'), x = -x; if (x > 9) write(x / 10); putchar(x % 10 + 48); } void write(char ch) { putchar(ch); } template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ...y) { write(x), write(y...); } const int maxn = 1010, maxm = 5010, inf = 1e9; int n, m, dep[maxn], fa[10][maxn], ans; vi e[maxn]; struct edge { int u, v, w; } a[maxm]; void dfs(int u) { for (int i = 1; i < 10; ++i) fa[i][u] = fa[i - 1][fa[i - 1][u]]; vi son; for (int v : e[u]) if (v != fa[0][u]) dep[v] = dep[u] + 1, fa[0][v] = u, dfs(v), son.push_back(v); e[u] = son; } int lca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); for (int i = 9; i >= 0; --i) if (dep[u] - dep[v] >= (1 << i)) u = fa[i][u]; if (u == v) return u; for (int i = 9; i >= 0; --i) if (fa[i][u] != fa[i][v]) u = fa[i][u], v = fa[i][v]; return fa[0][u]; } vi vec[maxn], vec2[maxn]; int dp[maxn][maxm], f[2048]; void dfs2(int u) { vi &son = e[u]; int c = son.size(), S = (1 << c) - 1; for (int v : son) dfs2(v); fill(f, f + S + 1, -inf), f[0] = 0; auto trs = [&] (int s, int w) { for (int i = S; i >= 0; --i) if ((i & s) == s) f[i] = max(f[i], f[i ^ s] + w); }; for (int i = 0; i < c; ++i) trs(1 << i, dp[son[i]][0]); for (int i : vec2[u]) { if (a[i].u == u || a[i].v == u) { for (int j = 0; j < c; ++j) if (dp[son[j]][i] >= 0) trs(1 << j, dp[son[j]][i] + a[i].w); } else { for (int j = 0; j < c; ++j) if (dp[son[j]][i] >= 0) for (int k = j + 1; k < c; ++k) if (dp[son[k]][i] >= 0) trs((1 << j) | (1 << k), dp[son[j]][i] + dp[son[k]][i] + a[i].w); } } dp[u][0] = f[S]; for (int i = 0; i < c; ++i) { int v = son[i]; for (int j = 1; j <= m; ++j) dp[u][j] = max(dp[u][j], dp[v][j] + f[S ^ (1 << i)]); } for (int i : vec[u]) dp[u][i] = max(dp[u][i], f[S]); } int main() { read(n, m); vector <edge> ve; while (m--) { int u, v, w; read(u, v, w); if (!w) e[u].push_back(v), e[v].push_back(u); else ve.push_back({u, v, w}); } dfs(1), m = 0; for (edge p : ve) { ans += p.w; if (~(dep[p.u] ^ dep[p.v]) & 1) a[++m] = p; } for (int i = 1; i <= m; ++i) vec[a[i].u].push_back(i), vec[a[i].v].push_back(i), vec2[lca(a[i].u, a[i].v)].push_back(i); memset(dp, 0xaf, sizeof dp), dfs2(1); write(ans - dp[1][0], '\n'); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...