結果
問題 | No.421 しろくろチョコレート |
ユーザー | 37zigen |
提出日時 | 2016-09-09 01:24:13 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,391 bytes |
コンパイル時間 | 4,138 ms |
コンパイル使用メモリ | 85,140 KB |
実行使用メモリ | 64,476 KB |
最終ジャッジ日時 | 2024-04-28 00:53:49 |
合計ジャッジ時間 | 25,619 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 146 ms
54,164 KB |
testcase_01 | AC | 473 ms
64,476 KB |
testcase_02 | AC | 883 ms
60,436 KB |
testcase_03 | AC | 144 ms
55,196 KB |
testcase_04 | AC | 470 ms
61,132 KB |
testcase_05 | AC | 179 ms
56,880 KB |
testcase_06 | AC | 141 ms
53,956 KB |
testcase_07 | AC | 189 ms
56,640 KB |
testcase_08 | WA | - |
testcase_09 | AC | 148 ms
41,372 KB |
testcase_10 | AC | 191 ms
45,688 KB |
testcase_11 | AC | 193 ms
46,112 KB |
testcase_12 | AC | 130 ms
41,504 KB |
testcase_13 | AC | 133 ms
41,464 KB |
testcase_14 | AC | 116 ms
40,312 KB |
testcase_15 | AC | 119 ms
40,744 KB |
testcase_16 | AC | 252 ms
47,176 KB |
testcase_17 | AC | 245 ms
46,860 KB |
testcase_18 | AC | 225 ms
47,180 KB |
testcase_19 | AC | 117 ms
40,128 KB |
testcase_20 | AC | 208 ms
46,756 KB |
testcase_21 | AC | 220 ms
46,880 KB |
testcase_22 | AC | 201 ms
45,868 KB |
testcase_23 | AC | 131 ms
41,308 KB |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | AC | 274 ms
46,320 KB |
testcase_29 | AC | 253 ms
46,952 KB |
testcase_30 | AC | 251 ms
46,340 KB |
testcase_31 | AC | 239 ms
47,152 KB |
testcase_32 | AC | 240 ms
47,012 KB |
testcase_33 | AC | 262 ms
47,016 KB |
testcase_34 | AC | 1,175 ms
47,368 KB |
testcase_35 | AC | 1,228 ms
47,152 KB |
testcase_36 | AC | 280 ms
45,844 KB |
testcase_37 | AC | 249 ms
46,912 KB |
testcase_38 | AC | 219 ms
47,124 KB |
testcase_39 | AC | 676 ms
47,952 KB |
testcase_40 | AC | 208 ms
46,048 KB |
testcase_41 | AC | 155 ms
43,144 KB |
testcase_42 | AC | 172 ms
43,612 KB |
testcase_43 | AC | 560 ms
50,680 KB |
testcase_44 | AC | 208 ms
46,376 KB |
testcase_45 | AC | 400 ms
49,816 KB |
testcase_46 | AC | 229 ms
45,100 KB |
testcase_47 | WA | - |
testcase_48 | AC | 209 ms
46,304 KB |
testcase_49 | AC | 928 ms
49,948 KB |
testcase_50 | WA | - |
testcase_51 | AC | 238 ms
46,784 KB |
testcase_52 | AC | 218 ms
46,260 KB |
testcase_53 | AC | 424 ms
49,808 KB |
testcase_54 | AC | 1,076 ms
47,512 KB |
testcase_55 | AC | 149 ms
44,492 KB |
testcase_56 | AC | 147 ms
44,264 KB |
testcase_57 | AC | 210 ms
45,776 KB |
testcase_58 | AC | 319 ms
47,104 KB |
testcase_59 | AC | 185 ms
45,996 KB |
testcase_60 | AC | 229 ms
46,960 KB |
testcase_61 | AC | 201 ms
46,244 KB |
testcase_62 | AC | 123 ms
40,536 KB |
testcase_63 | AC | 120 ms
40,156 KB |
testcase_64 | AC | 134 ms
41,508 KB |
ソースコード
package No400番台; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Q421 { public static void main(String[] args) { new Q421().solver(); } int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; int h, w; char[][] choco; int[][] comp; void solver() { Scanner sc = new Scanner(System.in); h = sc.nextInt(); w = sc.nextInt(); choco = new char[h][w]; for (int i = 0; i < h; i++) { choco[i] = sc.next().toCharArray(); } comp = new int[h][w]; for (int i = 0; i < h; i++) { Arrays.fill(comp[i], -1); } int color = 0; int ans = 0; int odd = 0, even = 0; for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { if (on_filed(x, y) && comp[y][x] == -1) { ArrayList<Integer>[] g = new ArrayList[h * w]; for (int i = 0; i < h * w; i++) { g[i] = new ArrayList<>(); } ArrayDeque<Pair> que = new ArrayDeque<>(); que.add(new Pair(x, y)); while (!que.isEmpty()) { Pair p = que.poll(); if (comp[p.y][p.x] != -1) continue; comp[p.y][p.x] = color; if ((p.x + p.y) % 2 == 0) even++; else odd++; for (int i = 0; i < 4; i++) { int nx = p.x + dx[i]; int ny = p.y + dy[i]; if (on_filed(nx, ny) && comp[ny][nx] == -1) { int a = id(p.x, p.y); int b = id(nx, ny); g[a].add(b); g[b].add(a); que.add(new Pair(nx, ny)); } } } int the_number_of_matchings = bipartiteMatching(g, (h * w) / 2); ans += the_number_of_matchings * 100; even -= the_number_of_matchings; odd -= the_number_of_matchings; color++; } } } // show_comp(); int common = Math.min(even, odd); ans += common * 10; even -= common; odd -= common; ans += even + odd; System.out.println(ans); } int id(int x, int y) { if ((y + x) % 2 == 0) return (y * w + x) / 2; else return (y * w + x) / 2 + (h * w - 1) / 2 + 1; } boolean on_filed(int x, int y) { if (0 <= x && x < w && 0 <= y && y < h && choco[y][x] != '.') { return true; } else return false; } class Pair { int x; int y; Pair(int x, int y) { this.x = x; this.y = y; } } boolean augment(ArrayList<Integer>[] g, int u, Integer[] matchTo, Boolean[] visited) { if (u < 0) return true; for (int v : g[u]) { if (!visited[v]) { visited[v] = true; if (augment(g, matchTo[v], matchTo, visited)) { matchTo[u] = v; matchTo[v] = u; return true; } } } return false; } int bipartiteMatching(ArrayList<Integer>[] g, int L) { final int n = g.length; Integer[] matchTo = new Integer[n]; Arrays.fill(matchTo, -1); matching = new ArrayList<>(); int match = 0; for (int i = 0; i < L; i++) { Boolean[] visited = new Boolean[n]; Arrays.fill(visited, false); if (augment(g, i, matchTo, visited)) match++; } for (int i = 0; i < L; i++) { if (matchTo[i] > 0) matching.add(new Edge(i, matchTo[i])); } return match; } ArrayList<Edge> matching; class Edge { int a; int b; Edge(int a, int b) { this.a = a; this.b = b; } } void show_comp() { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { System.out.print((comp[i][j] == -1 ? "#" : comp[i][j]) + " "); } System.out.println(); } } }