結果
| 問題 |
No.348 カゴメカゴメ
|
| コンテスト | |
| ユーザー |
 moti
|
| 提出日時 | 2015-10-19 14:21:43 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 4,917 bytes |
| コンパイル時間 | 1,030 ms |
| コンパイル使用メモリ | 102,692 KB |
| 最終ジャッジ日時 | 2024-11-14 19:20:20 |
| 合計ジャッジ時間 | 2,611 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:40:11: error: ‘in_range’ function uses ‘auto’ type specifier without trailing return type
40 | constexpr auto in_range(int x, int y) {
| ^~~~
main.cpp:40:11: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:44:1: error: ‘draw’ function uses ‘auto’ type specifier without trailing return type
44 | auto draw(int x, int y, char c, char nc) {
| ^~~~
main.cpp:44:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:62:1: error: ‘find_outer_land’ function uses ‘auto’ type specifier without trailing return type
62 | auto find_outer_land() {
| ^~~~
main.cpp:62:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:70:1: error: ‘make_tree’ function uses ‘auto’ type specifier without trailing return type
70 | auto make_tree() {
| ^~~~
main.cpp:70:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp:135:1: error: ‘rec’ function uses ‘auto’ type specifier without trailing return type
135 | auto rec(int curr, bool par_used = true) {
| ^~~~
main.cpp:135:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
ソースコード
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <fstream>
using namespace std;
#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
auto write_graph() -> void;
constexpr int Max = 1000*1000+1;
constexpr int dx[] = {-1,0,1,0,-1,1,1,-1};
constexpr int dy[] = {0,-1,0,1,-1,-1,1,1};
constexpr char VisMark = ' ';
constexpr char RingMark = 'o';
int N, M;
vector<string> in;
vector<int> tree[Max];
constexpr auto in_range(int x, int y) {
return 0<=x&&x<M && 0<=y&&y<N;
}
auto draw(int x, int y, char c, char nc) {
queue<pair<int, int>> q;
q.emplace(x, y);
while(!q.empty()) {
auto p = q.front(); q.pop();
int x = p.first, y = p.second;
rep(i, 8) {
int nx = x+dx[i], ny = y+dy[i];
if(!in_range(nx, ny)) { continue; }
if(in[ny][nx] != c) { continue; }
in[ny][nx] = nc;
q.emplace(nx, ny);
}
}
}
auto find_outer_land() {
rep(i, N) { if(in[i][0] == '.') return make_pair(0, i); if(in[i][M-1] == '.') return make_pair(M-1, i); }
rep(i, M) { if(in[0][i] == '.') return make_pair(i, 0); if(in[N-1][i] == '.') return make_pair(i, N-1); }
assert(false);
}
auto make_tree() {
queue<tuple<int, int, int>> nodeQ;
// 外側の . をみつける
auto outer_land = find_outer_land();
int next_node = 0;
nodeQ.emplace(outer_land.first, outer_land.second, next_node++);
// BFS木を作るBFS
while(!nodeQ.empty()) {
auto const nodeQP = nodeQ.front(); nodeQ.pop();
queue<pair<int, int>> q;
q.emplace(get<0>(nodeQP), get<1>(nodeQP));
in[get<1>(nodeQP)][get<0>(nodeQP)] = VisMark;
vector<pair<int, int>> next_node_list;
// 次の深さの輪を見つけるために、同じ深さの'.'を訪れるBFS
while(!q.empty()) {
auto const p = q.front(); q.pop();
auto const x = get<0>(p), y = get<1>(p);
rep(i, 8) {
auto const nx = x+dx[i], ny = y+dy[i];
if(!in_range(nx, ny)) { continue; }
// '.' は訪れるだけ
if(in[ny][nx] == '.') {
if(i > 3 && in[y+dy[i-4]][x+dx[i-4]] != '.' && in[y+dy[(i-3)%4]][x+dx[(i-3)%4]] != '.') { continue; }
in[ny][nx] = VisMark;
q.emplace(nx, ny);
}
// 'x' は輪の要素なので、一つ見つけてあとは塗りつぶす
if(in[ny][nx] == 'x') {
draw(nx, ny, 'x', RingMark);
next_node_list.emplace_back(nx, ny);
}
}
}
/*
rep(i, N) cout << in[i] << endl;
cout << "\n\n";
*/
auto const node = get<2>(nodeQP);
rep(i, next_node_list.size()) {
tree[node].push_back(next_node);
// add_edge(node, next_node);
int x = next_node_list[i].first, y = next_node_list[i].second;
rep(k, 8) {
int nx = x+dx[k], ny = y+dy[k];
if(!in_range(nx, ny)) { continue; }
if(in[ny][nx] == '.') {
nodeQ.emplace(nx, ny, next_node);
break;
}
}
next_node++;
}
}
}
ll dp[1000*1000+1][2];
auto rec(int curr, bool par_used = true) {
ll& ret = dp[curr][par_used];
if(ret >= 0) { return ret; }
if(tree[curr].empty()) {
return ret = par_used ? 0 : 1;
}
if(par_used) {
ret = 0;
rep(i, tree[curr].size()) {
int tar = tree[curr][i];
ret += rec(tar, false);
}
}
else {
int r1 = 1;
rep(i, tree[curr].size()) {
int tar = tree[curr][i];
r1 += rec(tar, true);
}
int r2 = 0;
rep(i, tree[curr].size()) {
int tar = tree[curr][i];
r2 += rec(tar, false);
}
ret = max(r1, r2);
}
return ret;
}
auto main() -> int {
cin >> N >> M;
rep(i, N) {
string s; cin >> s; in.push_back(s);
assert(in[i].size() == M);
}
assert(in.size() == N);
rep(i, N) rep(j, M) assert(in[i][j] == '.' || in[i][j] == 'x');
rep(i, N) {
rep(j, M) {
if(in[i][j] != 'x') { continue; }
int xcount = 0;
rep(k, 8) {
int ni = i+dy[k], nj = j+dx[k];
if(!in_range(nj, ni)) { continue; }
xcount += in[ni][nj] == 'x';
}
assert(xcount == 2);
}
}
make_tree();
// write_graph();
memset(dp, -1, sizeof dp);
cout << rec(0) << endl;
return 0;
}
auto write_graph() -> void {
ofstream ofs("tree.dot");
ofs << "digraph G {\n";
rep(i, Max) {
for(auto const& tar: tree[i]) {
ofs << " " << i << " -> " << tar << ";\n";
}
}
ofs << "}\n";
ofs.close();
int ret, state;
ret = system("dot -Tpng tree.dot > tree.png");
if(WIFEXITED(ret)){
state = WEXITSTATUS(ret);
}
else{
state = -1;
}
printf("STATUS = %d\n", state);
// exit(ret);
}