Submission #2661442

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;

struct Kruskal{

  struct UnionFind{
    Int n;
    vector<Int> r,p;
    UnionFind(){}
    UnionFind(Int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
    Int find(Int x){
      return (x==p[x]?x:p[x]=find(p[x]));
    }
    bool same(Int x,Int y){
      return find(x)==find(y);
    }
    void unite(Int x,Int y){
      x=find(x);y=find(y);
      if(x==y) return;
      if(r[x]<r[y]) swap(x,y);
      r[x]+=r[y];
      p[y]=x;
    }
  };
  
  struct edge{
    Int from,to,cost,used;
    edge(){}
    edge(Int from,Int to,Int cost):
      from(from),to(to),cost(cost),used(0){}
    bool operator<(const edge& e) const{
      return cost<e.cost;
    }
  };

  Int n;
  vector<edge> edges;

  Kruskal(){}
  Kruskal(Int sz):n(sz){}
  
  void add_edge(Int u,Int v,Int c){
    edges.emplace_back(u,v,c);
  }

  void input(Int m,Int offset=0){
    Int a,b,c;
    for(Int i=0;i<m;i++){
      cin>>a>>b>>c;
      add_edge(a+offset,b+offset,c);
    }
  }
  
  Int build(){
    sort(edges.rbegin(),edges.rend());
    UnionFind uf(n+1);
    Int res=0;
    for(auto &e:edges){
      if(!uf.same(e.from,e.to)){
	res+=e.cost;
	uf.unite(e.from,e.to);
	e.used=1;
      }
    }
    return res;
  }
};


template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//INSERT ABOVE HERE
signed main(){
  Int h,w;
  cin>>h>>w;
  Int sx,sy,gx,gy;
  cin>>sx>>sy>>gx>>gy;
  auto a=make_v<Int>(h,w);
  for(Int i=0;i<h;i++)
    for(Int j=0;j<w;j++)
      cin>>a[i][j];

  auto idx=[&](Int y,Int x){return y*w+x;};
  Int ans=0;
  Kruskal G(h*w);
  for(Int i=0;i<h;i++){
    for(Int j=0;j<w;j++){
      ans+=a[i][j];
      if(i+1<h) G.add_edge(idx(i,j),idx(i+1,j),a[i][j]*a[i+1][j]);
      if(j+1<w) G.add_edge(idx(i,j),idx(i,j+1),a[i][j]*a[i][j+1]);
    }
  }
  ans+=G.build();
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result