#312276 (D) No.348 カゴメカゴメ

提出ソース

結果

問題	No.348 カゴメカゴメ
ユーザー	👑 hos.lyric
提出日時	2019-01-23 22:44:38
言語	D (dmd 2.106.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,184 ms 113,764 KB
testcase_01	AC	3 ms 5,376 KB
testcase_02	AC	1,344 ms 178,544 KB
testcase_03	AC	1,400 ms 105,344 KB
testcase_04	AC	4 ms 5,376 KB
testcase_05	AC	5 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	1 ms 5,376 KB
testcase_11	AC	1 ms 5,376 KB
testcase_12	AC	28 ms 10,752 KB
testcase_13	AC	10 ms 5,376 KB
testcase_14	AC	3 ms 5,376 KB
testcase_15	AC	1,008 ms 175,964 KB
testcase_16	AC	1 ms 6,944 KB
testcase_17	AC	1 ms 6,944 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	1 ms 6,944 KB
testcase_22	AC	1 ms 6,940 KB
testcase_23	AC	1,129 ms 163,076 KB
testcase_24	AC	1,104 ms 143,580 KB
testcase_25	AC	1,117 ms 143,540 KB
testcase_26	AC	1,103 ms 143,588 KB
testcase_27	AC	1,091 ms 143,672 KB
testcase_28	AC	1,117 ms 162,828 KB
testcase_29	AC	1,128 ms 143,572 KB
testcase_30	AC	1,141 ms 163,728 KB
testcase_31	AC	1,116 ms 143,560 KB
testcase_32	AC	1,114 ms 163,632 KB
testcase_33	AC	89 ms 20,724 KB
testcase_34	AC	87 ms 20,480 KB
testcase_35	AC	88 ms 20,736 KB
testcase_36	AC	89 ms 20,864 KB
testcase_37	AC	92 ms 20,864 KB
testcase_38	AC	87 ms 20,736 KB
testcase_39	AC	89 ms 20,736 KB
testcase_40	AC	90 ms 20,992 KB
testcase_41	AC	90 ms 20,864 KB
testcase_42	AC	90 ms 20,864 KB
testcase_43	AC	13 ms 5,376 KB
testcase_44	AC	13 ms 5,376 KB
testcase_45	AC	13 ms 5,376 KB
testcase_46	AC	13 ms 5,376 KB
testcase_47	AC	13 ms 5,376 KB
testcase_48	AC	12 ms 5,376 KB
testcase_49	AC	13 ms 5,376 KB
testcase_50	AC	13 ms 5,376 KB
testcase_51	AC	13 ms 5,376 KB
testcase_52	AC	13 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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) {
  }
}

yukicoder

結果

テストケース

ソースコード