library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub beet-aizu/library

:heavy_check_mark: graph/nicetree.cpp

Depends on

Verified with

Code

#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
Back to top page