結果
問題 | No.348 カゴメカゴメ |
ユーザー |
![]() |
提出日時 | 2020-04-16 00:10:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 959 ms / 2,000 ms |
コード長 | 2,156 bytes |
コンパイル時間 | 232 ms |
コンパイル使用メモリ | 82,556 KB |
実行使用メモリ | 182,940 KB |
最終ジャッジ日時 | 2024-10-01 19:08:49 |
合計ジャッジ時間 | 12,653 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 53 |
ソースコード
import sysread = sys.stdin.buffer.readreadline = sys.stdin.buffer.readlinereadlines = sys.stdin.buffer.readlinesfrom collections import defaultdictH, W = map(int, readline().split())A = [-1] * (W + 4)A += [-1] + [0] * (W + 2) + [-1]for _ in range(H):A += [-1, 0] + [1 * (x == ord('x')) for x in readline().rstrip()] + [0, -1]A += [-1] + [0] * (W + 2) + [-1]A += [-1] * (W + 4)H += 4W += 4N = H * Wroot = [0] * Nfor v in range(N):if A[v] or root[v]:continuestack = [v]root[v] = vwhile stack:v = stack.pop()for dx in (1, -1, W, -W):w = v + dxif A[w] or root[w]:continueroot[w] = root[v]stack.append(w)component_size = defaultdict(int)for v in range(N):if A[v] != 1:continuenbd0 = []nbdx = []for dx in (1, -1, W - 1, W, W + 1, -W - 1, -W, -W + 1):w = v + dxif A[w]:nbdx.append(w)continuer = root[w]if not nbd0:nbd0.append(r)elif nbd0[0] != r and nbd0[-1] != r:nbd0.append(r)if len(nbd0) == 1:# 三角形new_node = sum(pow(v, 10, 10 ** 9 + 7) for v in [v] + nbdx)nbd0.append(new_node)key = tuple(sorted(nbd0))component_size[key] += 1nodes = []for (u, v) in component_size:nodes.append(u)nodes.append(v)nodes = sorted(set(nodes))n_to_i = {n: i for i, n in enumerate(nodes)}N = len(nodes)if N == 0:print(0)exit()graph = [[] for _ in range(N)]for (u, v), x in component_size.items():u = n_to_i[u]v = n_to_i[v]graph[u].append((v, x))graph[v].append((u, x))# あとは 木 dproot = 0parent = [0] * Ncost = [0] * Norder = []stack = [root]while stack:x = stack.pop()order.append(x)for y, c in graph[x]:if y == parent[x]:continueparent[y] = xcost[y] = cstack.append(y)dp0 = [0] * Ndp1 = [0] * Nfor v in order[::-1][:-1]:p = parent[v]x = cost[v]dp0[p] += dp1[v]dp1[p] += max(dp0[v] + x, dp1[v])print(dp1[0])