This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |