Submission #2751303
Source Code Expand
#include <bits/stdc++.h>
#define REP(i,k,n) for(int(i)=(k);(i)<(n);++(i))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
int H,W;
int Sx, Sy, Gx, Gy; // no use?
int P[110][110];
// ** UnionFind **
class UnionFind {
private:
vector<int> par; // 親
vector<int> rank; // 木の深さ
public:
// n 要素で初期化
UnionFind(int n) {
par.resize(n); // or MAX_N
rank.resize(n);
REP(i,0,n) {
par[i] = i;
rank[i] = 0;
}
}
// 木の根を求める
int find(int x) {
if (par[x] == x) {
return x;
} else {
return par[x] = find(par[x]);
}
}
// xとyの属する集合を併合
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) {
par[x] = y;
} else {
par[y] = x;
if (rank[x] == rank[y]) rank[x]++;
}
}
// xとyが同じ集合に属するか否か
bool same(int x, int y) {
return find(x) == find(y);
}
};
// ** kruskal **
struct edge { int u, v, cost; };
bool comp(const edge& e1, const edge& e2) { // 逆順で,最大全域木にする
return e1.cost > e2.cost;
}
vector<edge> es;
int V, E;
int kruskal() {
sort(ALL(es), comp);
UnionFind uf(V); // UnionFindの初期化
int res = 0;
REP(i,0,E) {
edge e = es[i];
if (!uf.same(e.u, e.v)) {
uf.unite(e.u, e.v);
res += e.cost;
}
}
return res;
}
// ** End **
// 移動4方向のベクトル
// (1,0), (0,1), (-1,0), (0,-1)
// の4方向を表現している
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
// edge集合を1次元配列で扱うため
int encode_pair(int x, int y)
{
return y * W + x; // [0,HW)
}
int main()
{
cin >> H >> W;
cin >> Sx >> Sy >> Gx >> Gy;
REP(y,0,H) {
REP(x,0,W) {
cin >> P[x][y];
}
}
// Add edges
REP(y,0,H) {
REP(x,0,W) {
REP(i,0,4) { // 4方向
int nx = x + dx[i];
int ny = y + dy[i];
// 範囲内にあること
if (0 <= nx && nx < W && 0 <= ny && ny < H) {
int u = encode_pair(x,y);
int v = encode_pair(nx,ny);
int cost = P[x][y] * P[nx][ny]; // 負のコストに?
edge e = { u, v, cost };
es.push_back(e);
}
}
}
}
V = H * W;
E = es.size();
// 移動ボーナス
int res = kruskal();
// すべてのマスを訪れることによる得点
REP(y,0,H) {
REP(x,0,W) {
res += P[x][y];
}
}
cout << res << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - Game on a Grid |
User |
tdyydt |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2759 Byte |
Status |
AC |
Exec Time |
7 ms |
Memory |
1148 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
100 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt |
All |
subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_26.txt, subtask1_27.txt, subtask1_28.txt, subtask1_29.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample_01.txt |
AC |
1 ms |
256 KB |
subtask0_sample_02.txt |
AC |
1 ms |
256 KB |
subtask0_sample_03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
1 ms |
256 KB |
subtask1_02.txt |
AC |
1 ms |
256 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
1 ms |
256 KB |
subtask1_06.txt |
AC |
1 ms |
256 KB |
subtask1_07.txt |
AC |
7 ms |
1148 KB |
subtask1_08.txt |
AC |
7 ms |
1148 KB |
subtask1_09.txt |
AC |
7 ms |
1148 KB |
subtask1_10.txt |
AC |
7 ms |
1148 KB |
subtask1_11.txt |
AC |
7 ms |
1148 KB |
subtask1_12.txt |
AC |
7 ms |
1148 KB |
subtask1_13.txt |
AC |
7 ms |
1148 KB |
subtask1_14.txt |
AC |
7 ms |
1148 KB |
subtask1_15.txt |
AC |
7 ms |
1148 KB |
subtask1_16.txt |
AC |
6 ms |
1148 KB |
subtask1_17.txt |
AC |
1 ms |
256 KB |
subtask1_18.txt |
AC |
1 ms |
256 KB |
subtask1_19.txt |
AC |
1 ms |
256 KB |
subtask1_20.txt |
AC |
5 ms |
1148 KB |
subtask1_21.txt |
AC |
6 ms |
1148 KB |
subtask1_22.txt |
AC |
6 ms |
1148 KB |
subtask1_23.txt |
AC |
6 ms |
1148 KB |
subtask1_24.txt |
AC |
1 ms |
256 KB |
subtask1_25.txt |
AC |
1 ms |
256 KB |
subtask1_26.txt |
AC |
1 ms |
256 KB |
subtask1_27.txt |
AC |
1 ms |
256 KB |
subtask1_28.txt |
AC |
1 ms |
256 KB |
subtask1_29.txt |
AC |
1 ms |
256 KB |