Submission #799232

#TimeUsernameProblemLanguageResultExecution timeMemory
799232adrilenTraining (IOI07_training)C++17
100 / 100
15 ms4640 KiB
#pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; using ll = long long; using arr = array<int, 2>; using arrr = array<int, 3>; constexpr int maxn = 1e3 + 5, maxm = 5e3; int dp[maxn][1 << 10] = { 0 }; int parent[maxn] = { 0 }; basic_string <int> chld[maxn]; arrr edges[maxm]; basic_string<int>adj[maxn]; arr order[maxn] = { 0 }; int order_to_pos[maxn * 2 + 5] = { 0 }; int depth[maxn] = { 0 }; int t = 0; void fnd_tree(int p, int par, int dep) { depth[p] = dep; // order_to_pos[t] = p; order[p][0] = t++; for (int i : adj[p]) { if (i == par) continue; chld[p].push_back(i); parent[i] = p; fnd_tree(i, p, dep + 1); } order_to_pos[t] = p; order[p][1] = t++; } arr calc_upwards(int p, int fin, int fr) { if (p == fin && p == fr) return {0, (int)chld[p].size()}; int ind = 0; for (int i : chld[p]) { if (i == fr) break; ind++; } if (p == fin) return {0, ind}; arr r = calc_upwards(parent[p], fin, p); r[0] += (p == fr ? dp[p][(1 << (chld[p].size())) - 1] : dp[p][(1 << (chld[p].size())) - (1 << ind) - 1]); return r; } priority_queue<arrr, vector<arrr>, greater<arrr>> forw, backw; void dfs(int p) { vector<arrr> new_edges; for (int i : chld[p]) { while (!backw.empty() && backw.top()[0] <= order[p][1]) { new_edges.emplace_back(backw.top()); backw.pop(); } dfs(i); } while (!backw.empty() && backw.top()[0] <= order[p][1]) { new_edges.emplace_back(backw.top()); backw.pop(); } int s = chld[p].size(); vector<vector<int>>opt_edges(s + 1, vector<int>(s + 1)); for (int i = 0; i < s; i++) { opt_edges[i][s] = dp[chld[p][i]][(1 << (chld[chld[p][i]].size())) - 1]; for (int j = i + 1; j < s; j++) { opt_edges[i][j] = dp[chld[p][i]][(1 << (chld[chld[p][i]].size())) - 1] + dp[chld[p][j]][(1 << (chld[chld[p][j]].size())) - 1]; } } auto it = new_edges.begin(); arr l, r; arrr a; while (it != new_edges.end()) { a = *it++; a[0] = order_to_pos[a[0]]; l = calc_upwards(a[0], p, a[0]), r = calc_upwards(a[1], p, a[1]); if (l[1] > r[1]) swap(l, r); opt_edges[l[1]][r[1]] = max( opt_edges[l[1]][r[1]], l[0] + r[0] + a[2] ); } // Bitset dp for (int i = 1; i < (1 << s); i++) { for (int j = 0; j < s; j++) { if ((i & (1 << j)) == 0) continue; dp[p][i] = max(dp[p][i], dp[p][i - (1 << j)] + opt_edges[j][s]); for (int k = j + 1; k < s; k++) { if ((i & (1 << k)) == 0) continue; dp[p][i] = max(dp[p][i], dp[p][i - (1 << j) - (1 << k)] + opt_edges[j][k]); } } // if (__builtin_popcount(i) == 1) cout << "\n"; // cout << i << " " << dp[p][i] << "\t"; } // cout << "\n"; // Return new edges while (!forw.empty() && forw.top()[0] == order[p][1]) { a = forw.top(); forw.pop(); a[0] = order_to_pos[a[0]]; swap(a[0], a[1]); a[0] = order[a[0]][1]; backw.push(a); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; for (int i = 0; i < m; i++) { cin >> edges[i][0] >> edges[i][1] >> edges[i][2]; } sort(edges, edges + m, [](const auto &l, const auto &r) { return l[2] < r[2]; }); for (int i = 0; i < n - 1; i++) { adj[edges[i][0]].push_back(edges[i][1]); adj[edges[i][1]].push_back(edges[i][0]); } fnd_tree(1, 0, 0); int output = 0; for (int i = n - 1; i < m; i++) { output += edges[i][2]; if ((depth[edges[i][0]] ^ depth[edges[i][1]]) & 1) { continue; } if (order[edges[i][0]][1] > order[edges[i][1]][1]) swap(edges[i][0], edges[i][1]); edges[i][0] = order[edges[i][0]][1]; forw.push(edges[i]); } dfs(1); cout << output - dp[1][(1 << (chld[1].size())) - 1] << "\n"; assert(output >= 0); assert(forw.empty()); assert(backw.empty()); }
#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...