結果
問題 | No.348 カゴメカゴメ |
ユーザー | moti |
提出日時 | 2016-03-24 03:16:16 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 3,503 bytes |
コンパイル時間 | 1,640 ms |
コンパイル使用メモリ | 180,908 KB |
実行使用メモリ | 9,588 KB |
最終ジャッジ日時 | 2024-10-01 21:47:42 |
合計ジャッジ時間 | 3,931 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
8,008 KB |
testcase_01 | AC | 4 ms
7,148 KB |
testcase_02 | AC | 44 ms
9,588 KB |
testcase_03 | AC | 34 ms
8,308 KB |
testcase_04 | AC | 4 ms
6,972 KB |
testcase_05 | AC | 4 ms
7,940 KB |
testcase_06 | AC | 4 ms
7,208 KB |
testcase_07 | AC | 3 ms
6,944 KB |
testcase_08 | AC | 3 ms
7,872 KB |
testcase_09 | AC | 3 ms
7,128 KB |
testcase_10 | AC | 3 ms
6,944 KB |
testcase_11 | AC | 3 ms
7,036 KB |
testcase_12 | AC | 4 ms
7,204 KB |
testcase_13 | AC | 4 ms
7,080 KB |
testcase_14 | AC | 4 ms
8,260 KB |
testcase_15 | AC | 29 ms
8,188 KB |
testcase_16 | AC | 4 ms
6,968 KB |
testcase_17 | AC | 4 ms
7,136 KB |
testcase_18 | AC | 4 ms
6,976 KB |
testcase_19 | AC | 4 ms
7,012 KB |
testcase_20 | AC | 4 ms
7,272 KB |
testcase_21 | AC | 3 ms
7,752 KB |
testcase_22 | AC | 4 ms
8,264 KB |
testcase_23 | AC | 37 ms
8,084 KB |
testcase_24 | AC | 37 ms
8,540 KB |
testcase_25 | AC | 37 ms
8,372 KB |
testcase_26 | AC | 38 ms
8,140 KB |
testcase_27 | AC | 38 ms
8,336 KB |
testcase_28 | AC | 38 ms
8,512 KB |
testcase_29 | AC | 38 ms
8,308 KB |
testcase_30 | AC | 38 ms
8,300 KB |
testcase_31 | AC | 38 ms
8,148 KB |
testcase_32 | AC | 37 ms
8,392 KB |
testcase_33 | AC | 6 ms
7,364 KB |
testcase_34 | AC | 6 ms
7,176 KB |
testcase_35 | AC | 6 ms
7,748 KB |
testcase_36 | AC | 7 ms
7,312 KB |
testcase_37 | AC | 7 ms
7,592 KB |
testcase_38 | AC | 6 ms
7,456 KB |
testcase_39 | AC | 7 ms
7,876 KB |
testcase_40 | AC | 6 ms
7,876 KB |
testcase_41 | AC | 6 ms
7,276 KB |
testcase_42 | AC | 6 ms
7,704 KB |
testcase_43 | AC | 4 ms
7,032 KB |
testcase_44 | AC | 4 ms
7,392 KB |
testcase_45 | AC | 4 ms
7,224 KB |
testcase_46 | AC | 4 ms
7,488 KB |
testcase_47 | AC | 4 ms
6,944 KB |
testcase_48 | AC | 4 ms
7,276 KB |
testcase_49 | AC | 4 ms
7,040 KB |
testcase_50 | AC | 4 ms
7,204 KB |
testcase_51 | AC | 4 ms
6,988 KB |
testcase_52 | AC | 4 ms
7,364 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:116:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 116 | scanf("%d %d", &N, &M); | ~~~~~^~~~~~~~~~~~~~~~~ main.cpp:121:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 121 | scanf("%s", G[i]+1); | ~~~~~^~~~~~~~~~~~~~
ソースコード
// 入力をscanfにしたときの速度差テスト用 #include <bits/stdc++.h> using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) #define minus(c) memset(c, -1, sizeof c) const int Max = 110890; int dx[] = {-1,0,1,0,-1,1,1,-1}; int dy[] = {0,-1,0,1,-1,-1,1,1}; char VisMark = ' '; char RingMark = 'o'; int N, M; char G[1010][1010]; int ring_lens[Max]; vector<int> tree[Max]; // to, cost template<class T> constexpr bool in_range(T y, T x, T H, T W) { return 0<=y&&y<H&&0<=x&&x<W; } void make_tree() { auto get_ring_len = [](int sy, int sx) { int ret = 1; queue<pair<int, int>> q; q.emplace(sy, sx); G[sy][sx] = RingMark; while(!q.empty()) { int y, x; tie(y, x) = q.front(); q.pop(); rep(i, 8) { // 'x'は8方向 int ny = y + dy[i], nx = x + dx[i]; if(!in_range(ny, nx, N, M)) { continue; } if(G[ny][nx] != 'x') { continue; } G[ny][nx] = RingMark; ret ++; q.emplace(ny, nx); } } return ret; }; auto get_next_depth_ring = [&](int sy, int sx) { vector<tuple<int, int, int>> ret; queue<pair<int, int>> q; q.emplace(sy, sx); G[sy][sx] = VisMark; // 次の深さの輪を見つけるために、同じ深さ輪の間の '.' を訪れるBFS while(!q.empty()) { int y, x; tie(y, x) = q.front(); q.pop(); rep(i, 4) { // 4方向で輪を跨がずに'.'を消す int ny = y + dy[i], nx = x + dx[i]; if(!in_range(ny, nx, N, M)) { continue; } // 同じ深さの輪の間の '.' if(G[ny][nx] == '.') { G[ny][nx] = VisMark; q.emplace(ny, nx); } // 'x' は輪の要素なので、一つ見つけてあとは塗りつぶす if(G[ny][nx] == 'x') { ret.emplace_back(ny, nx, get_ring_len(ny, nx)); } } } return std::move(ret); }; // 同じ深さの木の葉が左から並ぶ (y, x, ノード番号) // '.'が連続する領域をノードと捉える queue<tuple<int, int, int>> leaves; leaves.emplace(0, 0, 0); int nextch = 1; // BFS木を作る while(!leaves.empty()) { int ly, lx, leaf; tie(ly, lx, leaf) = leaves.front(); leaves.pop(); auto ring_nodes = get_next_depth_ring(ly, lx); for(auto && e: ring_nodes) { int y, x, len; tie(y, x, len) = e; tree[leaf].emplace_back(nextch); ring_lens[nextch] = len; rep(k, 8) { // 8方向で輪を跨ぐ'.'を見つける int ny = y + dy[k], nx = x + dx[k]; if(!in_range(ny, nx, N, M)) { continue; } if(G[ny][nx] == '.') { leaves.emplace(ny, nx, nextch); break; } } nextch++; } } } int dp[Max][2]; int rec(int curr, bool par_used = true) { auto& ret = dp[curr][par_used]; if(ret + 1) { return ret; } if(tree[curr].empty()) { return ret = par_used ? 0 : ring_lens[curr]; } ret = 0; if(par_used) { rep(i, tree[curr].size()) { ret += rec(tree[curr][i], false); } } else { int r1 = ring_lens[curr]; for(auto && e: tree[curr]) { r1 += rec(e, true); } int r2 = 0; for(auto && e: tree[curr]) { r2 += rec(e, false); } ret = max(r1, r2); } return ret; } int main() { scanf("%d %d", &N, &M); N += 2, M += 2; rep(i, M) G[0][i] = '.'; REP(i, 1, N-1) { G[i][0] = '.'; scanf("%s", G[i]+1); G[i][M-1] = '.'; } rep(i, M) G[N-1][i] = '.'; make_tree(); minus(dp); cout << rec(0) << endl; return 0; }