#include <bits/stdc++.h>
#include "race.h"
using namespace std;
int subSize(int st, vector<pair<int,int>>(&g)[], int sz[], int par, bitset<200010> rem){
sz[st]=1;
for(pair<int,int> p : g[st]){
int c = p.first;
if(rem[c]||c==par) continue;
sz[st]+=subSize(c,g,sz,st,rem);
}
return sz[st];
}
int findCentroid(int node, vector<pair<int,int>>(&g)[], int siz, bitset<200010> rem, int par, int sizes[]){
for(pair<int,int> p : g[node]){
int c = p.first;
if(c==par||rem[c]) continue;
if(sizes[c]*2>siz){
return findCentroid(c,g,siz,rem,node,sizes);
}
}
return node;
}
void findLens(int st, vector<pair<int,int>>(&g)[], bitset<200010> rem, int par, unordered_map<int,int>(&mp), int dep, int len){
for(pair<int,int> p : g[st]){
int c = p.first;
int d = p.second;
if(c==par||rem[c]) continue;
if(mp[dep+d]==0){
mp[dep+d]=len+1;
}
else{
mp[dep+d]=min(mp[dep+d],len+1);
}
findLens(c,g,rem,st,mp,dep+d,len+1);
}
}
int buildDecomp(int node, vector<pair<int,int>>(&g)[], bitset<200010> rem, int sz[], int k){
int centroid = findCentroid(node,g,subSize(node,g,sz,-1,rem),rem,-1,sz);
int ans = 2e9;
unordered_map<int,int>mp;
rem[centroid]=1;
for(pair<int,int> p : g[centroid]){
int c = p.first;
if(rem[c]) continue;
unordered_map<int,int>temp;
temp[p.second]=1;
findLens(c,g,rem,centroid,temp,p.second,1);
for(pair<int,int>pa : temp){
if(mp[k-pa.first]){
ans=min(ans,mp[k-pa.first]+pa.second);
}
else{
mp.erase(k-pa.first);
}
}
for(pair<int,int>pa:temp){
if(mp[pa.first]){
mp[pa.first]=min(mp[pa.first],pa.second);
}
else{
mp[pa.first]=pa.second;
}
}
}
if(mp[k]){
ans=min(ans,mp[k]);
}
else{
mp.erase(k);
}
for(pair<int,int>p:g[centroid]){
int c = p.first;
if(rem[c])continue;
ans=min(ans,buildDecomp(c,g,rem,sz,k));
}
return ans;
}
int best_path(int n, int k, int e[][2], int w[])
{
vector<pair<int,int>>g[n];
for(int i = 0;i<n-1;i++){
g[e[i][0]].push_back({e[i][1],w[i]});
g[e[i][1]].push_back({e[i][0],w[i]});
}
bool rem[n];
int sz[n];
fill(rem,rem+n,0);
int ans = buildDecomp(0,g,rem,sz,k);
if(ans==2e9){
return -1;
}
else{
return ans;
}
}
Compilation message
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:94:31: error: could not convert '(bool*)(& rem)' from 'bool*' to 'std::bitset<200010>'
94 | int ans = buildDecomp(0,g,rem,sz,k);
| ^~~
| |
| bool*
