結果

問題 No.348 カゴメカゴメ
ユーザー nebukuro09nebukuro09
提出日時 2018-04-16 16:37:16
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 711 ms / 2,000 ms
コード長 3,829 bytes
コンパイル時間 1,672 ms
コンパイル使用メモリ 170,916 KB
実行使用メモリ 32,892 KB
最終ジャッジ日時 2023-09-03 19:35:46
合計ジャッジ時間 15,650 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 598 ms
21,248 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 711 ms
32,892 KB
testcase_03 AC 598 ms
16,740 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 17 ms
4,380 KB
testcase_13 AC 6 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 15 ms
15,176 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 1 ms
4,376 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 1 ms
4,376 KB
testcase_23 AC 662 ms
22,696 KB
testcase_24 AC 672 ms
23,300 KB
testcase_25 AC 658 ms
23,040 KB
testcase_26 AC 663 ms
22,280 KB
testcase_27 AC 659 ms
22,192 KB
testcase_28 AC 680 ms
22,248 KB
testcase_29 AC 665 ms
22,656 KB
testcase_30 AC 674 ms
22,832 KB
testcase_31 AC 658 ms
22,752 KB
testcase_32 AC 664 ms
22,548 KB
testcase_33 AC 50 ms
4,792 KB
testcase_34 AC 50 ms
4,804 KB
testcase_35 AC 49 ms
4,860 KB
testcase_36 AC 49 ms
4,780 KB
testcase_37 AC 50 ms
4,736 KB
testcase_38 AC 50 ms
4,916 KB
testcase_39 AC 50 ms
6,176 KB
testcase_40 AC 50 ms
4,856 KB
testcase_41 AC 50 ms
4,712 KB
testcase_42 AC 49 ms
4,764 KB
testcase_43 AC 8 ms
4,376 KB
testcase_44 AC 7 ms
4,380 KB
testcase_45 AC 8 ms
4,376 KB
testcase_46 AC 7 ms
4,376 KB
testcase_47 AC 8 ms
4,380 KB
testcase_48 AC 8 ms
4,380 KB
testcase_49 AC 8 ms
4,376 KB
testcase_50 AC 8 ms
4,376 KB
testcase_51 AC 7 ms
4,376 KB
testcase_52 AC 7 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

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;
    }
}
0