Submission #784312

#TimeUsernameProblemLanguageResultExecution timeMemory
784312phoebeTraining (IOI07_training)C++17
100 / 100
125 ms41420 KiB
#include <bits/stdc++.h> using namespace std; // #define int long long #define ll long long #define pii pair<int, int> #define F first #define S second #define PB push_back #define ALL(x) x.begin(), x.end() #define FOR(i, n) for (int i = 0; i < n; i++) #define NYOOM ios::sync_with_stdio(0); cin.tie(0); #define endl '\n' const int INF = 1e9 + 7; const ll LLINF = 1ll<<60; const int maxn = 1e3 + 10; int n, m, h[maxn], jump[maxn][11], get_idx[maxn], dp[10][1<<10][maxn]; map<pii, int> path; vector<int> adj[maxn], x[maxn]; vector<pair<pii, int>> edge; vector<pair<pii, pii>> connections[maxn]; // {{cost, child}, {node, node_child}} void dfs(int v, int p, int height){ jump[v][0] = p; h[v] = height; int idx = 0; for (auto u : adj[v]){ if (u == p) continue; get_idx[u] = idx++; x[v].PB(u); dfs(u, v, height + 1); } } void lca_add(int a, int b, int c){ // h[a] >= h[b] int start_a = a, start_b = b; for (int p = 10; p >= 0; p--){ if (h[jump[a][p]] > h[b]) a = jump[a][p]; } if (jump[a][0] == b){ connections[a].PB({{c, a}, {b, start_a}}); return; } if (h[jump[a][0]] == h[b]) a = jump[a][0]; for (int p = 10; p >= 0; p--){ if (jump[a][p] != jump[b][p]) a = jump[a][p], b = jump[b][p]; } connections[a].PB({{c, start_a}, {b, start_b}}); connections[b].PB({{c, start_b}, {a, start_a}}); } int solve(int idx, int mask, int p); int path_cost(int p, int v){ if (path.count({p, v})) return path[{p, v}]; int re = 0, last = -1; while (v != p){ int mask = 0; if (last != -1) mask |= (1<<get_idx[last]); re += solve(0, mask, v); last = v; v = jump[v][0]; } path[{p, v}] = re; return re; } int solve(int idx, int mask, int p){ if (idx >= x[p].size()) return 0; if (dp[idx][mask][p] != -1) return dp[idx][mask][p]; int v = x[p][idx]; int re = solve(idx + 1, mask, p); // takent if (mask&(1<<idx)) return re; re += solve(0, 0, v); int take_mask = mask|(1<<idx); for (auto c : connections[v]){ int cost = c.F.F, child = c.F.S, u = c.S.F, u_child = c.S.S; if (get_idx[u] < idx && u != p) continue; if (mask&(1<<get_idx[u]) && u != p) continue; int take = 0; if (u == p){ // connects to parent take = solve(idx + 1, take_mask, p) + cost; take += path_cost(p, u_child); } else{ take = solve(idx + 1, take_mask|(1<<get_idx[u]), p) + cost; take += path_cost(p, child); take += path_cost(p, u_child); } re = max(re, take); } dp[idx][mask][p] = re; return dp[idx][mask][p]; } signed main(){ NYOOM; fill(&dp[0][0][0], &dp[0][0][0] + 10 * (1<<10) * maxn, -1); cin >> n >> m; int sum = 0; FOR(i, m){ int a, b, c; cin >> a >> b >> c; sum += c; if (c == 0){ adj[a].PB(b); adj[b].PB(a); } else{ edge.PB({{a, b}, c}); } } dfs(1, 1, 0); for (int p = 1; p <= 10; p++){ for (int i = 1; i <= n; i++){ jump[i][p] = jump[jump[i][p - 1]][p - 1]; } } for (auto x : edge){ int a = x.F.F, b = x.F.S, c = x.S; if (abs(h[a] - h[b]) % 2){ // if connects two nodes odd dist apart = can't include continue; } if (h[a] < h[b]) swap(a, b); lca_add(a, b, c); } cout << sum - solve(0, 0, 1); }

Compilation message (stderr)

training.cpp: In function 'int solve(int, int, int)':
training.cpp:69:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     if (idx >= x[p].size()) 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...