Submission #447141

#TimeUsernameProblemLanguageResultExecution timeMemory
447141SirCovidThe19thTraining (IOI07_training)C++14
100 / 100
19 ms4588 KiB
#include <bits/stdc++.h> using namespace std; struct edge{ int a, b, w; }; const int mx = 1005; int n, m, ans, dep[mx], cnt, par[mx], pos[mx], deg[mx], dp[mx][(1<<10)]; vector<int> adj[mx]; vector<edge> noPave, evenPth[mx]; void dfs(int i){ for (int x : adj[i]) if (x != par[i]) dep[x] = dep[i]+1, par[x] = i, pos[x] = (1<<deg[i]++), dfs(x); }int LCA(int a, int b){ while (dep[a] > dep[b]) a = par[a]; while (dep[b] > dep[a]) b = par[b]; while (a != b) a = par[a], b = par[b]; return a; }void solve(int i){ for (int x : adj[i]) if (x != par[i]) solve(x); for (int msk = 0; msk < (1<<deg[i]); msk++) for (int x : adj[i]) if (x != par[x] and !(msk&pos[x])) dp[i][msk] += dp[x][0]; for (auto r : evenPth[i]){ int sum = r.w, p1 = 0, p2 = 0; for (int x = r.a; x != i; p1 = pos[x], x = par[x]) sum += dp[x][p1]; for (int x = r.b; x != i; p2 = pos[x], x = par[x]) sum += dp[x][p2]; for (int msk = 0; msk < (1<<deg[i]); msk++) if (!(msk&p1) and !(msk&p2)) dp[i][msk] = max(dp[i][msk], dp[i][(msk|p1|p2)]+sum); } } int main(){ cin >> n >> m; for (int i = 0; i < m; i++){ int a, b, w; cin >> a >> b >> w; ans += w; if (!w) adj[a].push_back(b), adj[b].push_back(a); else noPave.push_back({a, b, w}); }dfs(1); for (auto r : noPave) if ((dep[r.a]+dep[r.b])%2 == 0) evenPth[LCA(r.a, r.b)].push_back(r); solve(1); cout<<ans-dp[1][0]<<endl; }
#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...