datastructure/skewheap.cpp

• View this file on GitHub
• Last update: 2020-10-27 19:32:25+09:00
• Link: https://atcoder.jp/contests/apc001/tasks/apc001_d

Depends on

• datastructure/unionfind.cpp

Required by

• algorithm/optimalbinarytree.cpp

Verified with

• test/aoj/2415.test.cpp
• test/aoj/ALDS1_9_C.test.cpp

Code

#ifndef call_from_test
#include <bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T, typename E>
struct SkewHeap{
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  using C = function<bool(T,T)>;
  G g;
  H h;
  C c;
  T INF;
  E ei;
  SkewHeap(G g,H h,C c,T INF,E ei):g(g),h(h),c(c),INF(INF),ei(ei){}

  struct Node{
    Node *l,*r;
    T val;
    E add;
    Node(T val,E add):val(val),add(add){l=r=nullptr;}
  };

  void eval(Node *a){
    if(a==nullptr) return;
    if(a->add==ei) return;
    if(a->l) a->l->add=h(a->l->add,a->add);
    if(a->r) a->r->add=h(a->r->add,a->add);
    a->val=g(a->val,a->add);
    a->add=ei;
  }

  T top(Node *a){
    return a!=nullptr?g(a->val,a->add):INF;
  }

  T snd(Node *a){
    eval(a);
    return a!=nullptr?min(top(a->l),top(a->r)):INF;
  }

  Node* add(Node *a,E d){
    if(a!=nullptr) a->add=h(a->add,d);
    return a;
  }

  Node* push(T v){
    return new Node(v,ei);
  }

  Node* meld(Node *a,Node *b){
    if(!a or !b) return a?a:b;
    if(c(top(a),top(b))) swap(a,b);
    eval(a);
    a->r=meld(a->r,b);
    swap(a->l,a->r);
    return a;
  }

  Node* pop(Node* a){
    eval(a);
    auto res=meld(a->l,a->r);
    delete a;
    return res;
  }
};
//END CUT HERE
#ifndef call_from_test

#define call_from_test
#include "unionfind.cpp"
#undef call_from_test

signed APC001_D(){
  using ll = long long;
  using Heap = SkewHeap<ll, ll>;
  ll n,m;
  cin>>n>>m;
  vector<ll> a(n);
  for(ll i=0;i<n;i++) cin>>a[i];

  auto g=[](ll a,ll b){return a+b;};
  auto h=[](ll a,ll b){return a+b;};
  auto c=[](ll a,ll b){return a>b;};

  const ll INF = 1e16;
  Heap heap(g,h,c,INF,0);
  vector<Heap::Node*> v(n);
  for(ll i=0;i<n;i++) v[i]=heap.push(a[i]);

  UnionFind uf(n);
  for(ll i=0;i<m;i++){
    ll x,y;
    cin>>x>>y;
    x=uf.find(x);y=uf.find(y);
    uf.unite(x,y);
    if(uf.find(x)!=x) swap(x,y);
    v[x]=heap.meld(v[x],v[y]);
    v[y]=NULL;
  }

  if(m==n-1){
    cout<<0<<endl;
    return 0;
  }

  Heap::Node* base=NULL;

  ll ans=0,cnt=0;
  for(ll i=0;i<n;i++){
    if(uf.find(i)==i){
      ans+=heap.top(v[i]);
      v[i]=heap.pop(v[i]);
      base=heap.meld(base,v[i]);
      cnt++;
    }
  }

  while(m*2+cnt<(n-1)*2){
    if(base==NULL){
      cout<<"Impossible"<<endl;
      return 0;
    }
    ans+=heap.top(base);
    base=heap.pop(base);
    cnt++;
  }

  cout<<ans<<endl;
  return 0;
}
/*
  verified on 2019/12/17
  https://atcoder.jp/contests/apc001/tasks/apc001_d
*/

signed main(){
  APC001_D();
}
#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: datastructure/skewheap.cpp: line 72: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page