結果

問題 No.348 カゴメカゴメ
コンテスト
ユーザー hos.lyric
提出日時 2019-01-23 22:44:38
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 1,400 ms / 2,000 ms
コード長 4,715 bytes
コンパイル時間 1,117 ms
コンパイル使用メモリ 126,532 KB
実行使用メモリ 178,544 KB
最終ジャッジ日時 2024-06-13 03:35:47
合計ジャッジ時間 22,121 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }
real readReal() { return readToken.to!real; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


int root(int[] uf, int u) {
  return (uf[u] < 0) ? u : (uf[u] = uf.root(uf[u]));
}
bool connect(int[] uf, int u, int v) {
  u = uf.root(u);
  v = uf.root(v);
  if (u == v) return false;
  if (uf[u] > uf[v]) swap(u, v);
  uf[u] += uf[v];
  uf[v] = u;
  return true;
}


int M, N;
string[] A;

int[][] G;
int[] scores;

// (discard, use)
Tuple!(int, int) dfs(int u) {
  auto ret = tuple(0, scores[u]);
  foreach (v; G[u]) {
    auto res = dfs(v);
    ret[0] += max(res[0], res[1]);
    ret[1] += res[0];
  }
  return ret;
}

void main() {
  try {
    for (; ; ) {
      M = readInt();
      N = readInt();
      A = new string[M + 2];
      foreach (x; [0, M + 1]) {
        foreach (y; 0 .. N + 2) {
          A[x] ~= ".";
        }
      }
      foreach (x; 1 .. M + 1) {
        A[x] = "." ~ readToken() ~ ".";
      }
      M += 2;
      N += 2;
      
      auto uf = new int[M * N];
      uf[] = -1;
      foreach (x; 0 .. M) foreach (y; 0 .. N) {
        if (A[x][y] == 'x') {
          foreach (dir; 0 .. 4) {
            const xx = x + [+1, +1, 0, -1, -1, -1, 0, +1][dir];
            const yy = y + [0, +1, +1, +1, 0, -1, -1, -1][dir];
            if (0 <= xx && xx < M && 0 <= yy && yy < N && A[xx][yy] == 'x') {
              uf.connect(x * N + y, xx * N + yy);
            }
          }
        }
      }
      int V = 1;
      auto ids = new int[][](M, N);
      foreach (x; 0 .. M) foreach (y; 0 .. N) {
        ids[x][y] = -1;
      }
      foreach (x; 0 .. M) foreach (y; 0 .. N) {
        if (A[x][y] == 'x' && uf[x * N + y] < 0) {
          ids[x][y] = V++;
        }
      }
      foreach (x; 0 .. M) foreach (y; 0 .. N) {
        if (A[x][y] == 'x') {
          const r = uf.root(x * N + y);
          ids[x][y] = ids[r / N][r % N];
        }
      }
      debug {
        writeln("ids");
        foreach (x; 0 .. M) {
          writeln(ids[x]);
        }
      }
      
      // 0-1 BFS from outside
      // (depth, last ring)
      auto q = DList!(Tuple!(int, int))();
      auto d = new Tuple!(int, int)[][](M, N);
      auto vis = new bool[][](M, N);
      foreach (x; 0 .. M) foreach (y; 0 .. N) {
        d[x][y] = tuple(M * N, -1);
        vis[x][y] = false;
      }
      d[0][0] = tuple(0, 0);
      q.insertBack(tuple(0, 0));
      for (; !q.empty; ) {
        const x = q.front[0];
        const y = q.front[1];
        q.removeFront;
        if (!vis[x][y]) {
          vis[x][y] = true;
          const cc = (A[x][y] == 'x') ? tuple(d[x][y][0] + 1, ids[x][y]) : d[x][y];
          foreach (dir; 0 .. 4) {
            int xx = x + [+1, 0, -1, 0][dir];
            int yy = y + [0, +1, 0, -1][dir];
            if (0 <= xx && xx < M && 0 <= yy && yy < N) {
              if (d[xx][yy] > cc) {
                d[xx][yy] = cc;
                (A[x][y] == 'x') ? q.insertBack(tuple(xx, yy)) : q.insertFront(tuple(xx, yy));
              }
            }
          }
        }
      }
      debug {
        writeln("d[][][0]");
        foreach (x; 0 .. M) {
          writeln(d[x].map!"a[0]");
        }
        writeln("d[][][1]");
        foreach (x; 0 .. M) {
          writeln(d[x].map!"a[1]");
        }
      }
      
      G = new int[][V];
      scores = new int[V];
      foreach (x; 0 .. M) foreach (y; 0 .. N) {
        if (A[x][y] == 'x' && uf[x * N + y] < 0) {
          G[d[x][y][1]] ~= ids[x][y];
          scores[ids[x][y]] = -uf[x * N + y];
        }
      }
      debug {
        writeln("G = ", G);
        writeln("scores = ", scores);
      }
      auto res = dfs(0);
      writeln(res[0]);
    }
  } catch (EOFException e) {
  }
}
0