Submission #996849

#TimeUsernameProblemLanguageResultExecution timeMemory
996849GhettoTraining (IOI07_training)C++17
100 / 100
269 ms114260 KiB
#pragma GCC optimize("O3", "unroll-loops") #include <bits/stdc++.h> using namespace std; const short MAX_N = 1e3 + 5, MAX_M = 4e3 + 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(short u = 1, short par = -1) { n_inds++, ind[u] = n_inds; for (short 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 (short i = 1; i <= 19; i++) for (short u = 1; u <= n; u++) anc[u][i] = anc[anc[u][i - 1]][i - 1]; } short lca(short u, short v) { auto is_anc = [](short u, short 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 (short 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 (short i = 1; i <= m; i++) { val_sum += edge[i].val; short w = lca(edge[i].u, edge[i].v); short 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 = [](short u, short i, short 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(short u = 1) { for (short v : children[u]) dfs2(v); for (short i : paths[u]) { trans[i] = edge[i].val; for (short v : path[i]) { if (v == u) continue; int mask = (1 << children[v].size()) - 1; for (short 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 (short i = 0; i <= (short) children[u].size() - 1; i++) { if (!(mask & (1 << i))) continue; short v = children[u][i]; dp[u][mask] += dp[v][(1 << children[v].size()) - 1]; } for (short i : paths[u]) { bool halt = false; for (short v : path_children[i][u]) if (!(mask & (1 << child_ind[v]))) halt = true; if (halt) continue; int new_mask = mask; for (short 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; short new_m = 0; for (short 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 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...