Submission #2717377

---

Source Code Expand

#include <bits/stdc++.h>
#define INF 1000000000
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;

class UnionFindTree{
	private:
		int N;
		unique_ptr<int[]> parent;
		unique_ptr<int[]> rank;
		unique_ptr<int[]> size;
	public:
		UnionFindTree(int N){
			this -> N = N;
			this -> parent = make_unique<int[]>(N);
			this -> rank = make_unique<int[]>(N);
			this -> size = make_unique<int[]>(N);
			for(int i = 0; i < (int) N; i++){
				parent[i] = i; rank[i] = 0; size[i] = 1;
			}
		}
		void init(){
			for(int i = 0; i < (int) N; i++){
				parent[i] = i; rank[i] = 0; size[i] = 1;
			}
		}
		int find(int x){
			if(parent[x] == x) return x;
			else return parent[x] = find(parent[x]);
		}
		void unite(int x, int y){
			x = find(x); y = find(y);
			if(x == y) return;

			if(rank[x] < rank[y]){
				parent[x] = y;
				size[y] += size[x];
			}else{
				parent[y] = x;
				size[x] += size[y];
				if(rank[x] == rank[y]) rank[x]++;
			}
		}
		bool same(int x, int y){
			return find(x) == find(y);
		}
		int count(int x){
			return size[find(x)];
		}
};

struct edge{
	int from, to;
	int point;
};


bool comp(const edge& e1, const edge& e2){
	return e1.point > e2.point;
}

int main(void){
	int H, W; cin >> H >> W;
	int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy;
	int p[100][100];
	ll res = 0;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			cin >> p[j][i];
			res += p[j][i];
		}
	}

	int dx[] = {0, 1};
	int dy[] = {1, 0};
	vector<edge> G;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			for(int k = 0; k < 2; k++){
				int nx = j+dx[k], ny = i+dy[k];
				if(nx<W and ny<H){
					edge e = {W*i+j, W*ny+nx, p[j][i]*p[nx][ny]};
					G.push_back(e);
				}
			}
		}
	}

	UnionFindTree uf(H*W);
	sort(begin(G), end(G), comp);
	for(int i = 0; i < (int)G.size(); i++){
		edge e = G[i];
		if(not uf.same(e.from, e.to)){
			uf.unite(e.from, e.to);
			res += e.point;
		}
	}

	cout << res << '\n';

	return 0;
}

Submission Info

Judge Result