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
AC × 3
AC × 32
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