Submission #794129

#TimeUsernameProblemLanguageResultExecution timeMemory
794129boyliguanhanTraining (IOI07_training)C++17
30 / 100
11 ms8348 KiB
#include<bits/stdc++.h> using namespace std; vector<int> adj[1024]; struct npe { int a, b, c; }; vector<npe>b[1024],edge; int dep[1024], p[1024]; void dfs(int n) { for(auto i: adj[n]) if(i!=p[n]) p[i] = n, dep[i] = dep[n]+1, dfs(i); } int lca(int a, int b){ while(dep[a]>dep[b]) a = p[a]; while(dep[b]>dep[a]) b = p[b]; while(a-b) a = p[a], b = p[b]; return a; } int dp[1024][1024], bit[1024], ith[10]; void solve(int n) { int cnt = 0; for(auto i: adj[n]) if(i!=p[n]) solve(i); for(auto i: adj[n]) if(i!=p[n]) ith[cnt] = i, bit[i] = 1<<cnt++; int temp[1024]{}; for(int mask = 0; mask < 1<<cnt; mask++) for(int i = 0; i < cnt; i++) if(!(mask&1<<i)) temp[mask]+=dp[ith[i]][0]; for(auto x: b[n]) { int res = x.c, a = x.a, b = x.b; if(a!=n){ res+=dp[a][0]; for(;p[a]!=n;a=p[a]) res+=dp[p[a]][bit[a]]; } if(b!=n){ res+=dp[b][0]; for(;p[b]!=n;b=p[b]) res+=dp[p[b]][bit[b]]; } for(int mask = 0; mask < 1<<cnt; mask++) if(!(mask&(bit[x.a]|bit[x.b]))) temp[mask] = max(temp[mask],dp[n][mask|bit[x.a]|bit[x.b]]+res); } swap(dp[n], temp); } int main() { int n, m,sum=0; cin >> n >> m; while(m--) { int a, b, c; cin >> a >> b >> c; if(c) edge.push_back({a,b,c}), sum+=c; else adj[a].push_back(b),adj[b].push_back(a); } dfs(1); for(npe i: edge) if(1^(dep[i.a]+dep[i.b])%2) b[lca(i.a,i.b)].push_back(i); solve(1); cout << sum - dp[1][0] << '\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...