Submission #778691

#TimeUsernameProblemLanguageResultExecution timeMemory
778691PoonYaPatTraining (IOI07_training)C++14
30 / 100
6 ms4692 KiB
#include <bits/stdc++.h> using namespace std; struct edg { int a,b,w; }; int n,m,dp[1005][1<<10],level[1005],p[1005],ss,mmax[1005]; vector<int> adj[1005],adj2[1005]; vector<edg> edge,e[1005]; void dfs (int x, int par) { level[x]=level[par]+1; p[x]=par; for (auto s : adj[x]) if (s!=par) dfs(s,x), adj2[x].push_back(s); } void dfs2(int x) { int k=adj2[x].size(); for (int i=0; i<k; ++i) { int s=adj2[x][i]; dfs2(s); dp[x][1<<i]=dp[s][mmax[s]]; } for (auto s : e[x]) { int a=s.a, b=s.b, sum=s.w, k1=-1, k2=-1; int now=p[a], pre=a; if (a!=x) { sum+=dp[pre][mmax[pre]]; while (now!=x) { int k=lower_bound(adj2[now].begin(),adj2[now].end(),pre)-adj2[now].begin(); sum+=dp[now][mmax[now]^(1<<k)]; pre=now; now=p[now]; } k1=lower_bound(adj2[x].begin(),adj2[x].end(),pre)-adj2[x].begin(); } now=p[b]; pre=b; if (b!=x) { sum+=dp[pre][mmax[pre]]; while (now!=x) { int k=lower_bound(adj2[now].begin(),adj2[now].end(),pre)-adj2[now].begin(); sum+=dp[now][mmax[now]^(1<<k)]; pre=now; now=p[now]; } k2=lower_bound(adj2[x].begin(),adj2[x].end(),pre)-adj2[x].begin(); } if (k1==-1) dp[x][1<<k2]=max(dp[x][1<<k2],sum); else if (k2==-1) dp[x][1<<k1]=max(dp[x][1<<k1],sum); else dp[x][(1<<k1)|(1<<k2)]=max(dp[x][(1<<k1)|(1<<k2)],sum); } for (int mask=1; mask<(1<<k); ++mask) { int st=-1; for (int j=0; j<k; ++j) { if (mask&(1<<j)) { if (st=-1) { st=j; dp[x][mask]=max(dp[x][mask],dp[x][1<<j]+dp[x][mask^(1<<j)]); } else { dp[x][mask]=max(dp[x][mask],dp[x][(1<<st)|(1<<j)]+dp[x][mask^(1<<st)^(1<<j)]); } } } } } void solve(int X, int Y, int w) { int x=X, y=Y; if (level[x]<level[y]) swap(x,y); int dif=level[x]-level[y]; while (dif--) x=p[x]; while (x!=y) x=p[x],y=p[y]; if ((level[X]+level[Y]-2*level[x])%2==0) e[x].push_back({X,Y,w}); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for (int i=0; i<m; ++i) { int a,b,w; cin>>a>>b>>w; if (w==0) { adj[a].push_back(b); adj[b].push_back(a); } else edge.push_back({a,b,w}); ss+=w; } dfs(1,0); for (int i=1; i<=n; ++i) sort(adj2[i].begin(),adj2[i].end()), mmax[i]=(1<<(adj2[i].size()))-1; for (auto s : edge) solve(s.a,s.b,s.w); dfs2(1); cout<<ss-dp[1][mmax[1]]; }

Compilation message (stderr)

training.cpp: In function 'void dfs2(int)':
training.cpp:62:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   62 |                 if (st=-1) {
      |                     ~~^~~
#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...