Submission #697246

#TimeUsernameProblemLanguageResultExecution timeMemory
697246vjudge1Training (IOI07_training)C++17
100 / 100
15 ms6892 KiB
#include<bits/stdc++.h> using namespace std; const int N=1e3+10,M=5e3+10; vector<int>ed[N]; int n,m,dp[N][1<<9],X[M],Y[M],W[M],num[N][N]; int f[N],dfn[N],id[N],dep[N],ct; struct node{ int num,val; bool operator<(const node b)const{ return val<b.val; } }; struct RMQ{ node st[N][21]; RMQ(){} RMQ(int a[],int len){ for(int i=1;i<=len;i++)st[i][0]=node{a[i],dep[a[i]]}; for(int o=1;o<=20;o++){ for(int i=1;i+(1<<o)-1<=len;i++){ st[i][o]=min(st[i][o-1],st[i+(1<<(o-1))][o-1]); } } } int query(int l,int r){ if(l==r)return l; if(id[l]>id[r])swap(l,r); l=id[l]+1,r=id[r]; int len=r-l+1,k=__lg(len); return f[min(st[l][k],st[r-(1<<k)+1][k]).num]; } }ty; void dfs(int x,int fa){ f[x]=fa; dfn[++ct]=x; id[x]=ct; dep[x]=dep[fa]+1; for(int v:ed[x]){ if(v==fa)continue; dfs(v,x); } } int dis(int x,int y){ return dep[x]+dep[y]-dep[ty.query(x,y)]*2; } tuple<int,int,int>calc(int x,int y){ int lca=ty.query(x,y),res=0; if(x!=lca)while(f[x]!=lca){ res+=dp[f[x]][1<<num[f[x]][x]]; x=f[x]; } if(y!=lca)while(f[y]!=lca){ res+=dp[f[y]][1<<num[f[y]][y]]; y=f[y]; } return {x,y,res}; } vector<tuple<int,int,int>>vec[N]; void solve(int x,int fa){ int sz=0; vector<int>son; for(int v:ed[x]){ if(v==fa)continue; solve(v,x); num[x][v]=sz; sz++; son.push_back(v); } num[x][x]=-1; for(int i=0;i<1<<sz;i++){ for(int o=0;o<sz;o++){ if(!(i&(1<<o)))dp[x][i]+=dp[son[o]][0]; } } for(auto [p,q,w]:vec[x]){ auto [s1,s2,res]=calc(p,q); int val=res+w; if(p!=x)val+=dp[p][0]; if(q!=x)val+=dp[q][0]; s1=num[x][s1],s2=num[x][s2]; if(s1>s2)swap(s1,s2); if(s1==-1){ for(int i=0;i<1<<sz;i++){ if((i&(1<<s2)))dp[x][i^(1<<s2)]=max(dp[x][i^(1<<s2)],dp[x][i]+val); } } else{ for(int i=0;i<1<<sz;i++){ if((i&(1<<s1))&&(i&(1<<s2)))dp[x][i^(1<<s1)^(1<<s2)]=max(dp[x][i^(1<<s1)^(1<<s2)],dp[x][i]+val); } } } } int main(){ scanf("%d%d",&n,&m); int ans=0; for(int i=1;i<=m;i++)scanf("%d%d%d",&X[i],&Y[i],&W[i]),ans+=W[i]; for(int i=1;i<=m;i++)if(!W[i])ed[X[i]].push_back(Y[i]),ed[Y[i]].push_back(X[i]); dfs(1,0); ty=RMQ(dfn,n); for(int i=1;i<=m;i++)if(W[i]&&!(dis(X[i],Y[i])&1))vec[ty.query(X[i],Y[i])].emplace_back(X[i],Y[i],W[i]); solve(1,0); printf("%d",ans-dp[1][0]); return 0; }

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
training.cpp:96:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     for(int i=1;i<=m;i++)scanf("%d%d%d",&X[i],&Y[i],&W[i]),ans+=W[i];
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...