Submission #598753

#TimeUsernameProblemLanguageResultExecution timeMemory
598753BobaaTraining (IOI07_training)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1 << 10; vector<int> E[N], lca[N], dob; int id[N], d[N], par[N], pre[N], pst[N], wsk, dp[N][N], dp2[N][5 * N], n, m; vector<pair<int, pair<int, int>>> edg, edg2; void dfs1(int v, int p) { pre[v] = wsk++; par[v] = p; d[v] = d[p] + 1; int sz = E[v].size(); for (int i = 0; i < sz; i++) if (E[v][i] == p) swap(E[v][i], E[v].back()); if (p != 0) E[v].pop_back(); for (int i = 0; i < sz; i++) { id[E[v][i]] = i; dfs1(E[v][i], v); } pst[v] = wsk; } void dfs2(int v) { for (int u : E[v]) { dfs2(u); dp[v][1 << id[u]] = dp2[u][0]; } for (int e : lca[v]) { int u = edg[e].second.first, w = edg[e].second.second; while (par[w] != v) w = par[w]; if (u == v) dp[v][1 << id[w]] = max(edg[e].first + dp2[w][e], dp[v][1 << id[w]]); else { while (par[u] != v) u = par[u]; dp[v][(1 << id[u]) + (1 << id[w])] = max(edg[e].first + dp2[u][e] + dp2[w][e], dp[v][(1 << id[u]) + (1 << id[w])]); } } for (int i = 0; i < (1 << E[v].size()); i++) for (int j = i; ; j = (j - 1) & i) { dp[v][i] = max(dp[v][i], dp[v][j] + dp[v][i - j]); if (j == 0) break; } for (int e : dob) { if (edg[e].second.first == v && pre[edg[e].second.second] >= pst[v]) dp2[v][e] = dp[v][(1 << E[v].size()) - 1]; if (edg[e].second.second == v) dp2[v][e] = dp[v][(1 << E[v].size()) - 1]; if (par[edg2[e].second.first] == (v ^ par[edg2[e].second.second)] == v) { if (par[edg2[e].second.first] == v) { dp2[v][e] = dp[v][(1 << E[v].size()) - 1 - (1 << id[edg2[e].second.first])] + dp2[edg2[e].second.first][e]; edg2[e].second.first = v; } if (par[edg2[e].second.second] == v) { dp2[v][e] = dp[v][(1 << E[v].size()) - 1 - (1 << id[edg2[e].second.second])] + dp2[edg2[e].second.second][e]; edg2[e].second.second = v; } } } dp2[v][0] = dp[v][(1 << E[v].size()) - 1]; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; int sm = 0; for (int i = 0, u, v, w; i < m; i++) { cin >> u >> v >> w; sm += w; edg.push_back({w, {u, v}}); if (w == 0) { E[u].push_back(v); E[v].push_back(u); } } dfs1(1, 0); sort(edg.begin(), edg.end()); for (int i = n - 1; i < m; i++) { if (pre[edg[i].second.first] > pre[edg[i].second.second]) swap(edg[i].second.first, edg[i].second.second); int u = edg[i].second.first, v = edg[i].second.second; if ((d[u] & 1) != (d[v] & 1)) continue; if (d[u] < d[v]) swap(u, v); while (d[u] > d[v]) u = par[u]; while (u != v) { u = par[u]; v = par[v]; } dob.push_back(i); lca[u].push_back(i); } edg2 = edg; dfs2(1); cout << sum - dp2[1][0]; }

Compilation message (stderr)

training.cpp: In function 'void dfs2(int)':
training.cpp:45:66: error: expected ']' before ')' token
   45 |   if (par[edg2[e].second.first] == (v ^ par[edg2[e].second.second)] == v) {
      |                                                                  ^
      |                                                                  ]
training.cpp:45:67: error: expected ')' before ']' token
   45 |   if (par[edg2[e].second.first] == (v ^ par[edg2[e].second.second)] == v) {
      |      ~                                                            ^
      |                                                                   )
training.cpp:45:67: error: expected primary-expression before ']' token
training.cpp: In function 'int main()':
training.cpp:90:10: error: 'sum' was not declared in this scope; did you mean 'sm'?
   90 |  cout << sum - dp2[1][0];
      |          ^~~
      |          sm