This documentation is automatically generated by online-judge-tools/verification-helper
#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
struct NiceTree{
vector< vector<int> > G;
vector< set<int> > ex;
vector<int> buff;
NiceTree(int n):G(n),ex(n),buff(n){}
void add_edge(int u,int v){
if(u>v) swap(u,v);
if(ex[u].count(v)) return;
G[u].emplace_back(v);
G[v].emplace_back(u);
ex[u].emplace(v);
}
enum Type{LEAF, JOIN, INTRODUCE, FORGET};
struct Node{
int type,is_root;
Node():type(-1),is_root(1){}
// index for G
vector<int> bag;
void add_vertex(int v){bag.emplace_back(v);}
// index for T
vector<int> child;
void add_child(int v){child.emplace_back(v);}
};
vector<Node> T;
void to_nice(){
for(auto &vs:T){
sort(vs.bag.begin(),vs.bag.end());
for(int c:vs.child) T[c].is_root=0;
}
stack<int> st;
for(int i=0;i<(int)T.size();i++)
if(T[i].is_root) st.emplace(i);
while(!st.empty()){
int v=st.top();st.pop();
while(T[v].child.size()>2){
Node r;
r.add_child(T[v].child.back());
T[v].child.pop_back();
r.add_child(T[v].child.back());
T[v].child.pop_back();
r.bag=T[v].bag;
T[v].add_child(T.size());
T.emplace_back(r);
}
if(T[v].child.size()==2){
for(auto &u:T[v].child){
if(T[u].bag!=T[v].bag){
Node r;
r.add_child(u);
r.bag=T[v].bag;
u=T.size();
T.emplace_back(r);
}
}
T[v].type=JOIN;
}
if(T[v].child.size()==1){
int &u=T[v].child[0];
vector<int> latte,malta;
auto &ps=T[v].bag;
auto &qs=T[u].bag;
set_difference(ps.begin(),ps.end(),qs.begin(),qs.end(),
back_inserter(latte));
set_difference(qs.begin(),qs.end(),ps.begin(),ps.end(),
back_inserter(malta));
if(latte.size()+malta.size()>1){
Node r;
r.add_child(u);
r.bag=T[v].bag;
if(!latte.empty()){
r.bag.erase(find(r.bag.begin(),r.bag.end(),latte.back()));
}else{
r.bag.emplace_back(malta.back());
}
u=T.size();
T.emplace_back(r);
}
if(T[v].bag.size()<T[u].bag.size()) T[v].type=FORGET;
if(T[v].bag.size()>T[u].bag.size()) T[v].type=INTRODUCE;
}
if(T[v].child.empty()){
if(T[v].bag.size()>1){
Node r;
r.bag=T[v].bag;
r.bag.pop_back();
T[v].type=INTRODUCE;
T[v].add_child(T.size());
T.emplace_back(r);
}else{
T[v].type=LEAF;
}
}
for(auto &u:T[v].child)
st.emplace(u);
}
for(auto &vs:T)
for(int c:vs.child) T[c].is_root=0;
}
// root = 0 (if connected)
void build(){
int n=G.size();
if(n<=3){
Node r;
for(int i=0;i<n;i++) r.add_vertex(i);
T=vector<Node>({r});
return to_nice();
}
vector<int> deg(n);
queue<int> que;
for(int i=0;i<n;i++){
deg[i]=G[i].size();
if(deg[i]<=2) que.emplace(i);
}
vector<int> used(n,-1);
T.emplace_back();
while(!que.empty()){
int v=que.front();que.pop();
if(deg[v]>2 or used[v]!=-1) continue;
Node r;
r.add_vertex(v);
int p=-1,q=-1;
for(int u:G[v]){
if(used[u]==-1){
(p==-1?p:q)=u;
r.add_vertex(u);
}else if(used[u]>=0){
r.add_child(used[u]);
used[u]=-2;
}
}
if(deg[v]==0){
used[v]=T.size();
T.emplace_back(r);
continue;
}
if(q==-1){
deg[p]--;
}else{
if(p>q) swap(p,q);
if(!ex[p].count(q)){
add_edge(p,q);
}else{
deg[p]--;
deg[q]--;
}
}
for(int u:G[v])
if(deg[u]<=2) que.emplace(u);
deg[v]=0;
used[v]=T.size();
T.emplace_back(r);
}
for(int i=0;i<n;i++){
if(deg[i]>0){
T={};
return;
}
}
T.front()=T.back();T.pop_back();
to_nice();
}
template<typename F1,typename F2,typename F3,typename F4>
void dfs(int v,F1 &leaf,F2 &join,F3 &introduce,F4 &forget){
const auto &chd=T[v].child;
for(int u:chd) dfs(u,leaf,join,introduce,forget);
if(T[v].type==LEAF){
leaf(v);
return;
}
if(T[v].type==JOIN){
join(v);
return;
}
const auto &bag=T[v].bag;
for(int i=0;i<(int)bag.size();i++)
buff[bag[i]]=1<<i;
const auto &chd_bag=T[chd[0]].bag;
int dif=0;
for(int b:bag) dif^=b;
for(int b:chd_bag) dif^=b;
if(T[v].type==INTRODUCE){
introduce(v,dif);
return;
}
if(T[v].type==FORGET){
forget(v,dif);
return;
}
}
};
//END CUT HERE
#ifndef call_from_test
#define call_from_test
#include "../tools/fastio.cpp"
#include "../tools/chminmax.cpp"
#undef call_from_test
signed CSA_SPECIAL_MVC(){
int n,m;
cin>>n>>m;
NiceTree G(n);
using P = pair<int, int>;
set<P> es;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
a--;b--;
G.add_edge(a,b);
es.emplace(a,b);
es.emplace(b,a);
}
G.build();
auto &T=G.T;
auto &buff=G.buff;
vector< vector<int> > dps(T.size());
const int INF = 1e9;
auto base=
[&](int v){
const auto &bag=T[v].bag;
auto &dp=dps[v];
dp.assign(1<<bag.size(),-INF);
};
auto leaf=
[&](int v){
base(v);
auto &dp=dps[v];
dp[0]=0;
dp[1]=1;
};
auto join=
[&](int v){
base(v);
const auto &chd=T[v].child;
auto &dp=dps[v];
for(int i=0;i<(int)dp.size();i++)
chmax(dp[i],dps[chd[0]][i]+dps[chd[1]][i]-__builtin_popcount(i));
};
auto introduce=
[&](int v,int add){
base(v);
const auto &chd=T[v].child;
const auto &chd_bag=T[chd[0]].bag;
const auto &pr=dps[chd[0]];
auto &dp=dps[v];
for(int i=0;i<(int)pr.size();i++){
int bit=0,valid=1;
for(int j=0;j<(int)chd_bag.size();j++){
if((~i>>j)&1) continue;
bit|=buff[chd_bag[j]];
valid&=!es.count(P(chd_bag[j],add));
}
assert(!(bit&buff[add]));
if(valid) chmax(dp[bit|buff[add]],pr[i]+1);
chmax(dp[bit],pr[i]);
}
};
auto forget=
[&](int v,int rmv){
base(v);
const auto &chd=T[v].child;
const auto &chd_bag=T[chd[0]].bag;
const auto &pr=dps[chd[0]];
auto &dp=dps[v];
for(int i=0;i<(int)pr.size();i++){
int bit=0;
for(int j=0;j<(int)chd_bag.size();j++){
if((~i>>j)&1) continue;
if(rmv!=chd_bag[j]) bit|=buff[chd_bag[j]];
}
chmax(dp[bit],pr[i]);
}
};
int ans=n;
for(int i=0;i<(int)T.size();i++){
if(!T[i].is_root) continue;
G.dfs(i,leaf,join,introduce,forget);
ans-=*max_element(dps[i].begin(),dps[i].end());
}
cout<<ans<<endl;
return 0;
}
/*
verified 2020/02/21
https://csacademy.com/contest/archive/task/special-mvc/statement/
*/
signed main(){
CSA_SPECIAL_MVC();
return 0;
}
#endif
Traceback (most recent call last):
File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
bundler.update(path)
File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 400, in update
raise BundleErrorAt(path, i + 1, "unable to process #include in #if / #ifdef / #ifndef other than include guards")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: graph/nicetree.cpp: line 226: unable to process #include in #if / #ifdef / #ifndef other than include guards