제출 #355302

#제출 시각아이디문제언어결과실행 시간메모리
355302kshitij_sodaniTraining (IOI07_training)C++14
30 / 100
50 ms45932 KiB
//#pragma GCC optimize("Ofast,unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long llo; #define mp make_pair #define pb push_back #define a first #define b second #define endl '\n' llo n,m; vector<llo> adj[2001]; vector<pair<pair<llo,llo>,llo>> pre[2001]; vector<pair<llo,llo>> pre2[2001]; vector<pair<llo,llo>> pre3[2001]; vector<llo> pre4[2001]; llo dp[2001][5001]; llo par[2001][20]; llo lev[2001]; llo st[2001]; llo ww[5001]; llo endd[2001]; llo val[2001][2001]; llo val2[2001]; llo co=0; llo dp2[2001]; llo ind2[2001]; void dfs(llo no,llo par2=-1,llo levv=0){ //cout<<no<<",,"<<par2<<endl; par[no][0]=par2;//par2; lev[no]=levv; st[no]=co; co++; for(auto j:adj[no]){ if(j!=par2){ dfs(j,no,levv+1); } } endd[no]=co-1; } /*llo tree[2001]; void u(llo i,llo j){ while(i<=2000){ tree[i]+=j; i+=(i&-i); } } llo ss(llo i){ llo su=0; while(i>0){ su+=tree[i]; i-=(i&-i); } return su; }*/ void dfs2(llo no,llo par=-1){ llo su=0; vector<llo> ac; for(auto j:adj[no]){ if(j!=par){ dfs2(j,no); su+=dp[j][0]; ind2[j]=ac.size(); ac.pb(j); } } dp[no][0]=su; for(auto j:ac){ val2[j]=0; for(auto i:ac){ val[j][i]=0; } } for(auto j:pre3[no]){ val2[j.a]=max(val2[j.a],dp[j.a][j.b]+ww[j.b]); } for(auto j:pre[no]){ val[j.a.a][j.a.b]=max(val[j.a.a][j.a.b],dp[j.a.a][j.b]+dp[j.a.b][j.b]+ww[j.b]); val[j.a.b][j.a.a]=val[j.a.a][j.a.b]; } if(ac.size()){ llo nn=ac.size(); for(llo j=0;j<(1<<nn);j++){ dp2[j]=0; for(llo i=0;i<nn;i++){ if((1<<i)&j){ dp2[j]=max(dp2[j],val2[ac[i]]+dp2[j-(1<<i)]); } } for(llo i=0;i<nn;i++){ for(llo k=i+1;k<nn;k++){ if((j&(1<<i)) and (j&(1<<k))){ dp2[j]=max(dp2[j],dp2[j-(1<<i)-(1<<k)]+val[ac[i]][ac[k]]); } } } } dp[no][0]=max(dp[no][0],dp2[(1<<nn)-1]); for(auto j:pre2[no]){ dp[no][j.b]=max(dp[no][j.b],dp2[(1<<nn)-1-(1<<ind2[j.a])]+dp[j.a][j.b]); } } for(auto j:pre4[no]){ dp[no][j]=max(dp[no][j],dp[no][0]); } /* for(auto j:adj[no]){ if(j!=par){ u(st[no]+2,dp[j]); u(endd[no]+2,-dp[j]); u(st[j]+1,-dp[j]); u(endd[no]+2,dp[j]); } }*/ /*llo xy=0; for(auto j:pre[no]){ llo aa=j.a.a; llo bb=j.a.b; if(bb==no){ swap(aa,bb); } if(aa==no){ dp[no]=max(dp[no],ss(st[bb]+1)+j.b); } else{ llo cur=j.b; cur+=ss(st[bb]+1); cur+=ss(st[aa]+1); cur-=dp[pre2[no][xy].a]; cur-=dp[pre2[no][xy].b]; dp[no]=max(dp[no],cur); } xy++; }*/ /*for(int i=0;i<=m-(n-1);i++){ cout<<dp[no][i]<<","; } cout<<endl; cout<<no<<","<<dp[no][0]<<endl;*/ } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m; vector<pair<pair<llo,llo>,llo>> ed; for(llo i=0;i<m;i++){ llo aa,bb,cc; cin>>aa>>bb>>cc; aa--; bb--; if(cc==0){ adj[aa].pb(bb); adj[bb].pb(aa); } else{ ed.pb({{aa,bb},cc}); } } /*llo cur=0; for(llo i=0;i<n;i++){ if(adj[i].size()==1){ cur=i; } }*/ /* for(llo i=0;i<n;i++){ cout<<par[i][0]<<":"; } cout<<endl;*/ dfs(0); /*for(llo i=0;i<n;i++){ cout<<par[i][0]<<":"; } cout<<endl; */ for(llo j=1;j<20;j++){ for(llo i=0;i<n;i++){ if(par[i][j-1]==-1){ par[i][j]=-1; } else{ par[i][j]=par[par[i][j-1]][j-1]; } } } llo ans=0; llo xy=0;; for(auto j:ed){ xy++; ww[xy]=j.b; if((lev[j.a.a]+lev[j.a.b])%2==1){ ans+=j.b; } else{ llo aa=j.a.a; llo bb=j.a.b; if(lev[aa]>lev[bb]){ swap(aa,bb); } llo aa2=aa; llo bb2=bb; llo dif=lev[bb]-lev[aa]; for(llo j=0;j<20;j++){ if((1<<j)&dif){ bb=par[bb][j]; } } if(aa==bb){ llo cur=bb2; while(par[cur][0]!=aa){ pre2[par[cur][0]].pb({cur,xy}); cur=par[cur][0]; } pre3[aa].pb({cur,xy}); pre4[bb2].pb(xy); // pre[aa2].pb({{aa2,bb2},j.b}); // pre2[aa2].pb({-1,-1}); // cout<<aa2<<","<<bb2<<","<<-1<<endl; } else{ for(llo j=19;j>=0;j--){ if(par[aa][j]!=par[bb][j]){ aa=par[aa][j]; bb=par[bb][j]; } } llo xx=par[aa][0]; llo cur=aa2; while(cur!=aa){ pre2[par[cur][0]].pb({cur,xy}); cur=par[cur][0]; } cur=bb2; while(cur!=bb){ pre2[par[cur][0]].pb({cur,xy}); cur=par[cur][0]; } pre[par[aa][0]].pb({{aa,bb},xy}); pre4[aa2].pb(xy); pre4[bb2].pb(xy); /*pre[par[aa][0]].pb({{aa2,bb2},j.b}); pre2[par[aa][0]].pb({aa,bb});*/ //cout<<aa2<<","<<bb2<<","<<aa<<","<<bb<<","<<par[aa][0]<<endl; } /* if(ind[j.a.a]<ind[j.a.b]){ pre[j.a.b].pb({j.a.a,j.b}); } else{ pre[j.a.a].pb({j.a.b,j.b}); }*/ ans+=j.b; } } dfs2(0); /* for(llo i=0;i<n;i++){ for(auto j:pre[ss[i]]){ dp[i+1]=max(dp[i+1],dp[ind[j.a]]+j.b); ans+=j.b; } dp[i+1]=max(dp[i+1],dp[i]); }*/ ans-=dp[0][0]; cout<<ans<<endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

training.cpp: In function 'int main()':
training.cpp:234:9: warning: unused variable 'xx' [-Wunused-variable]
  234 |     llo xx=par[aa][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...