Submission #442040

#TimeUsernameProblemLanguageResultExecution timeMemory
442040AutronTraining (IOI07_training)C++14
100 / 100
26 ms4548 KiB
#include <bits/stdc++.h> using namespace std; struct nod{ pair<int, int> fat; int d; vector<int> dp; vector<int> out; }; vector<nod> g; struct edge{ int a, b, c; int lca; }; vector<edge> e; int getlca(int a, int b){ while(a!=b){ if(g[a].d>g[b].d) a=g[a].fat.first; else b=g[b].fat.first; } return a; } void dfs(int x, int fat=0){ for(int i=0;i<g[x].out.size();++i){ auto &it=g[x].out[i]; if(it==fat) continue; g[it].fat={x, i}; g[it].d=g[x].d+1; dfs(it, x); } } int main(){ int n, m; cin>>n>>m; g.resize(n); for(int i=0;i<n;++i) g[i].dp.resize(1<<10); e.resize(m); int tot=0; for(int i=0;i<m;++i){ cin>>e[i].a>>e[i].b>>e[i].c; e[i].a--, e[i].b--; if(e[i].c==0){ g[e[i].a].out.push_back(e[i].b); g[e[i].b].out.push_back(e[i].a); } tot+=e[i].c; } dfs(0); for(int i=0;i<m;++i){ e[i].lca=getlca(e[i].a, e[i].b); } sort(e.begin(), e.end(), [&](edge x, edge y){ return g[x.lca].d>g[y.lca].d; }); for(int i=0;i<m;++i){ auto &x=e[i]; if(x.c&&((g[x.a].d%2)!=(g[x.b].d%2))) continue; int val=x.c; pair<int, int> a; for(a=make_pair(x.a, -1);a.first!=x.lca;a=g[a.first].fat){ if(a.second<0) val+=g[a.first].dp[0]; else val+=g[a.first].dp[1<<(a.second)]; } pair<int, int> b; for(b=make_pair(x.b, -1);b.first!=x.lca;b=g[b.first].fat){ if(b.second<0) val+=g[b.first].dp[0]; else val+=g[b.first].dp[1<<(b.second)]; } if(a.second==-1) a.second=0; else a.second=(1<<a.second); if(b.second==-1) b.second=0; else b.second=(1<<b.second); for(int mask=0;mask<(1<<(g[x.lca].out.size()));++mask){ if((mask&a.second)||(mask&b.second)) continue; g[x.lca].dp[mask]=max(g[x.lca].dp[mask], g[x.lca].dp[mask|a.second|b.second] + val); } } cout<<tot-g[0].dp[0]<<"\n"; }

Compilation message (stderr)

training.cpp: In function 'void dfs(int, int)':
training.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0;i<g[x].out.size();++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...