結果
問題 | No.348 カゴメカゴメ |
ユーザー |
|
提出日時 | 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 |
ソースコード
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;}}