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>
#define DIM 1010
using namespace std;
vector <int> L[DIM];
long long dp[DIM][1050],best[DIM];
struct muchie{
int x,y,cost;
};
vector <muchie> mch,v[DIM];
vector <pair<int,int> > w;
int level[DIM],fth[DIM],first[DIM],E[DIM*3],p[DIM*3];
pair <int,int> rmq[20][DIM*3];
int n,m,i,j,x,y,cost,k;
void dfs (int nod, int tata){
fth[nod] = tata;
level[nod] = 1 + level[tata];
E[++k] = nod;
first[nod] = k;
for (auto vecin : L[nod])
if (vecin != tata){
dfs (vecin,nod);
E[++k] = nod;
}
}
int get_lca (int x, int y){
int posx = first[x], posy = first[y];
if (posx > posy)
swap (posx,posy);
int nr = p[posy-posx+1];
pair <int,int> sol = min (rmq[nr][posx],rmq[nr][posy-(1<<nr)+1]);
return E[sol.second];
}
int get_poz (int x, int y){
for (int i=0;i<L[x].size();i++)
if (L[x][i] == y)
return i;
}
void dfs2 (int nod, int tata){
for (auto vecin : L[nod])
dfs2 (vecin,nod);
int sz = L[nod].size();
if (!sz)
return;
int maxi = (1<<sz);
w.clear(); /// toate starile din care pot sa actualizez dinamica
for (int bit=0;bit<sz;bit++){
int vecin = L[nod][bit];
w.push_back(make_pair( (1<<bit), best[vecin] ));
}
for (auto it : v[nod]){ /// nod e lca
int x = it.x, y = it.y, cost = it.cost;
if (x != nod && y != nod){
long long sum = best[x] + best[y] + cost;
int val = x, mask = 0;
while (fth[val] != nod){
int poz = get_poz (fth[val],val);
sum += dp[fth[val]][( (1<<L[fth[val]].size()) - 1 ) ^ (1<<poz)];
val = fth[val];
}
int pozx = get_poz (nod,val);
mask |= (1<<pozx);
val = y;
while (fth[val] != nod){
int poz = get_poz (fth[val],val);
sum += dp[fth[val]][( (1<<L[fth[val]].size()) - 1 ) ^ (1<<poz)];
val = fth[val];
}
int pozy = get_poz (nod,val);
mask |= (1<<pozy);
sum += dp[nod][((1<<L[nod].size()) - 1) ^ (1<<pozx) ^ (1<<pozy) ];
w.push_back(make_pair(mask,sum));
} else { /// am un singur lant
int val = (x != nod) ? (x) : (y);
int mask = 0;
long long sum = best[val] + cost;
while (fth[val] != nod){
int poz = get_poz (fth[val],val);
sum += dp[fth[val]][( (1<<L[fth[val]].size()) - 1 ) ^ (1<<poz)];
val = fth[val];
}
int poz = get_poz (nod,val);
mask |= (1<<poz);
sum += dp[nod][((1<<L[nod].size()) - 1) ^ (1<<poz)];
w.push_back(make_pair(mask,sum));
}
}
for (int mask=0;mask<maxi;mask++){
for (auto it : w)
if ( (it.first & mask) == it.first)
dp[nod][mask] = max (dp[nod][mask],dp[nod][mask^it.first] + it.second);
}
for (int mask=0;mask<maxi;mask++)
best[nod] = max (best[nod],dp[nod][mask]);
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
cin>>n>>m;
for (i=1;i<=m;i++){
cin>>x>>y>>cost;
if (!cost){
L[x].push_back(y);
L[y].push_back(x);
} else mch.push_back({x,y,cost});
}
dfs (1,0);
for (i=2;i<=n;i++){
for (j=0;j<L[i].size();j++)
if (L[i][j] == fth[i])
break;
swap (L[i][j],L[i].back());
L[i].pop_back();
}
for (i=1;i<=k;i++)
rmq[0][i] = make_pair(level[E[i]],i);
for (i=1;(1<<i)<=k;i++)
for (j=1;j<=k;j++){
rmq[i][j] = rmq[i-1][j];
if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<i-1)].first < rmq[i][j].first)
rmq[i][j] = rmq[i-1][j + (1<<i-1)];
}
for (i=2;i<=k;i++)
p[i] = p[i/2] + 1;
long long total = 0;
for (auto it : mch){
int x = it.x, y = it.y;
if (level[x] > level[y])
swap (x,y);
total += it.cost;
if ( (level[y] - level[x]) % 2 )
continue;
int lca = get_lca (x,y);
v[lca].push_back({x,y,it.cost});
}
dfs2 (1,0);
cout<<total - best[1];
return 0;
}
Compilation message (stderr)
training.cpp: In function 'int get_poz(int, int)':
training.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for (int i=0;i<L[x].size();i++)
| ~^~~~~~~~~~~~
training.cpp: In function 'int main()':
training.cpp:160:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for (j=0;j<L[i].size();j++)
| ~^~~~~~~~~~~~
training.cpp:173:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
173 | if (j + (1<<(i-1)) <= k && rmq[i-1][j + (1<<i-1)].first < rmq[i][j].first)
| ~^~
training.cpp:174:47: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
174 | rmq[i][j] = rmq[i-1][j + (1<<i-1)];
| ~^~
training.cpp: In function 'int get_poz(int, int)':
training.cpp:46:1: warning: control reaches end of non-void function [-Wreturn-type]
46 | }
| ^
# | 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... |