結果

問題 No.348 カゴメカゴメ
ユーザー nebukuro09nebukuro09
提出日時 2018-04-16 16:37:16
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 652 ms / 2,000 ms
コード長 3,829 bytes
コンパイル時間 1,579 ms
コンパイル使用メモリ 174,744 KB
実行使用メモリ 30,808 KB
最終ジャッジ日時 2024-06-13 00:29:47
合計ジャッジ時間 12,714 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;
void main() {
const int[] dr4 = [-1, 1, 0, 0];
const int[] dc4 = [0, 0, -1, 1];
const int[] dr8 = [-1, -1, -1, 0, 0, 1, 1, 1];
const int[] dc8 = [-1, 0, 1, -1, 1, -1, 0, 1];
auto s = readln.split.map!(to!int);
auto H = s[0] + 2;
auto W = s[1] + 2;
auto A = (H-2).iota.map!(_ => "." ~ readln.chomp ~ ".").array;
A = '.'.repeat().take(W).to!string ~ A ~ '.'.repeat().take(W).to!string;
auto uf = new UnionFind(H*W);
auto used = new bool[][](H, W);
void dfs(int r, int c, int sr, int sc) {
if (used[r][c]) return;
used[r][c] = true;
uf.unite(r*W+c, sr*W+sc);
foreach (i; 0..8) {
int nr = r + dr8[i];
int nc = c + dc8[i];
if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
if (used[nr][nc] || A[nr][nc] == '.') continue;
dfs(nr, nc, sr, sc);
}
}
foreach (i; 0..H) foreach (j; 0..W) if (!used[i][j] && A[i][j] == 'x') dfs(i, j, i, j);
int cnt = 0;
auto node_map = new int[](H*W);
node_map.fill(-1);
foreach (i; 0..H*W) if (uf.table[i] < -1) node_map[i] = cnt++;
foreach (i; 0..H*W) node_map[i] = node_map[uf.find(i)];
if (cnt == 0) {
writeln(0);
return;
}
auto size = new int[](cnt);
foreach (i; 0..H*W) if (uf.table[uf.find(i)] < -1) size[node_map[uf.find(i)]] = -uf.table[uf.find(i)];
used = new bool[][](H, W);
auto G = new int[][](cnt);
auto G_set = new bool[int][](cnt);
auto roots = new bool[](cnt);
auto q = new BinaryHeap!(Array!(Tuple!(int, int, int, int)), "a[2] > b[2]");
q.insert(tuple(0, 0, 1, -1));
while (!q.empty) {
auto t = q.front;
q.removeFront;
auto r = t[0];
auto c = t[1];
auto d = t[2];
auto last = t[3];
if (used[r][c]) continue;
used[r][c] = true;
int nd = d;
int nlast = last;
if (A[r][c] == 'x' && node_map[r*W+c] != last) {
if (last != -1) {
G_set[last][node_map[r*W+c]] = true;
G_set[node_map[r*W+c]][last] = true;
} else {
roots[node_map[r*W+c]] = true;
}
nd += 1;
nlast = node_map[r*W+c];
}
foreach (i; 0..4) {
int nr = r + dr4[i];
int nc = c + dc4[i];
if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
if (used[nr][nc]) continue;
q.insert(tuple(nr, nc, nd, nlast));
}
}
foreach (i; 0..cnt) G[i] = G_set[i].keys.array;
auto dp = new int[][](cnt, 2);
foreach (i; 0..cnt) dp[i].fill(-1);
int dfs2(int n, int p, int painted) {
if (dp[n][painted] >= 0) return dp[n][painted];
int ret = painted ? size[n] : 0;
foreach (m; G[n]) {
if (m == p) continue;
if (!painted) ret += max(dfs2(m, n, 1), dfs2(m, n, 0));
else ret += dfs2(m, n, 0);
}
dp[n][painted] = ret;
return ret;
}
int ans = 0;
foreach (i; 0..cnt) if (roots[i]) ans += max(dfs2(i, -1, 0), dfs2(i, -1, 1));
ans.writeln;
}
class UnionFind {
int N;
int[] table;
this(int n) {
N = n;
table = new int[](N);
fill(table, -1);
}
int find(int x) {
return table[x] < 0 ? x : (table[x] = find(table[x]));
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (table[x] > table[y]) swap(x, y);
table[x] += table[y];
table[y] = x;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0