結果
| 問題 |
No.640 76本のトロンボーン
|
| コンテスト | |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2018-01-27 04:25:55 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 6,872 bytes |
| コンパイル時間 | 2,849 ms |
| コンパイル使用メモリ | 208,264 KB |
| 最終ジャッジ日時 | 2025-01-05 08:00:35 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 13 WA * 2 |
ソースコード
#include <bits/stdc++.h>
#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
using ll = long long;
using ld = long double;
template <typename T>
vector<T> Vec(int n, T v)
{
return vector<T>(n, v);
}
template <class... Args>
auto Vec(int n, Args... args)
{
auto val = Vec(args...);
return vector<decltype(val)>(n, move(val));
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
os << "sz:" << v.size() << "\n[";
for (const auto& p : v) {
os << p << ",";
}
os << "]\n";
return os;
}
template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
os << "(" << p.first << "," << p.second
<< ")";
return os;
}
constexpr ll MOD = (ll)1e9 + 7LL;
constexpr ld PI = static_cast<ld>(3.1415926535898);
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;
struct Graph {
Graph(const int n)
{
edge.resize(n);
}
void addEdge(const int from, const int to)
{
edge[from].push_back(to);
edge[to].push_back(from);
}
vector<vector<int>> edge;
};
int N;
int ans;
void TateMaximumIndependentSet(const Graph& g, const vector<bool>& used)
{
for (int i = 0; i < 2 * N; i++) {
if (not used[i]) {
vector<bool> tmp = used;
tmp[i] = true;
for (const int to : g.edge[i]) {
if (not used[to]) {
tmp[to] = true;
}
}
int cnt = 1;
for (int j = 2 * N; j < 4 * N; j++) {
if (not tmp[j]) {
cnt++;
}
}
if (i < N) {
if (not tmp[3 * N - 1] and not tmp[4 * N - 1]) {
cnt--;
}
} else {
if (not tmp[2 * N] and not tmp[3 * N]) {
cnt--;
}
}
ans = max(ans, cnt);
}
}
}
void YokoMaximumIndependentSet(const Graph& g, const vector<bool>& used)
{
for (int i = 2 * N; i < 4 * N; i++) {
if (not used[i]) {
vector<bool> tmp = used;
tmp[i] = true;
for (const int to : g.edge[i]) {
if (not used[to]) {
tmp[to] = true;
}
}
int cnt = 1;
for (int j = 0; j < 2 * N; j++) {
if (not tmp[j]) {
cnt++;
}
}
if (i < 3 * N) {
if (not tmp[N - 1] and not tmp[2 * N - 1]) {
cnt--;
}
} else {
if (not tmp[0] and not tmp[N]) {
cnt--;
}
}
ans = max(ans, cnt);
}
}
}
void TateMaximumIndependentSet2(const Graph& g, const vector<bool>& used)
{
int cnt = 0;
for (int i = 0; i < N; i++) {
if (not used[i] and not used[i + N]) {
cnt++;
}
}
ans = max(ans, cnt);
}
void YokoMaximumIndependentSet2(const Graph& g, const vector<bool>& used)
{
int cnt = 0;
for (int i = 0; i < N; i++) {
if (not used[i + 2 * N] and not used[i + 3 * N]) {
cnt++;
}
}
ans = max(ans, cnt);
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> N;
vector<bool> ok(4 * N, true);
vector<vector<bool>> room(N, vector<bool>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
char c;
cin >> c;
room[i][j] = c == '.';
}
}
Graph g(4 * N);
int res = 4 * N;
vector<bool> usedv(4 * N, false);
for (int i = 0; i < 4 * N; i++) {
const bool tate1 = i < 2 * N;
const int offset1 = (i % (2 * N)) / N;
const int pos1 = (i % (2 * N)) % N;
for (int k = 0; k < N - 1; k++) {
if (tate1) {
if (not room[offset1 + k][pos1]) {
res--;
usedv[i] = true;
break;
}
} else {
if (not room[pos1][offset1 + k]) {
res--;
usedv[i] = true;
break;
}
}
}
}
for (int i = 0; i < N; i++) {
if (usedv[i]) {
continue;
}
g.addEdge(i, i + N);
if (i == 0) {
for (int j = 2 * N; j < 3 * N; j++) {
if (usedv[j]) {
continue;
}
const int y = (j - 2 * N) % N;
if (y < N - 1) {
g.addEdge(i, j);
}
}
} else if (i < N - 1) {
for (int j = 2 * N; j < 4 * N; j++) {
if (usedv[j]) {
continue;
}
const int y = (j - 2 * N) % N;
if (y < N - 1) {
g.addEdge(i, j);
}
}
} else {
for (int j = 3 * N; j < 4 * N; j++) {
if (usedv[j]) {
continue;
}
const int y = (j - 2 * N) % N;
if (y < N - 1) {
g.addEdge(i, j);
}
}
}
}
for (int i = N; i < 2 * N; i++) {
if (usedv[i]) {
continue;
}
if (i == 2 * N) {
for (int j = 2 * N; j < 3 * N; j++) {
if (usedv[j]) {
continue;
}
const int y = (j - 2 * N) % N;
if (y > 0) {
g.addEdge(i, j);
}
}
} else if (i < 2 * N - 1) {
for (int j = 2 * N; j < 4 * N; j++) {
if (usedv[j]) {
continue;
}
const int y = (j - 2 * N) % N;
if (y > 0) {
g.addEdge(i, j);
}
}
} else {
for (int j = 3 * N; j < 4 * N; j++) {
if (usedv[j]) {
continue;
}
const int y = (j - 2 * N) % N;
if (y > 0) {
g.addEdge(i, j);
}
}
}
}
for (int i = 2 * N; i < 3 * N; i++) {
if (usedv[i] or usedv[i + N]) {
continue;
}
g.addEdge(i, i + N);
}
if (usedv[0] or usedv[N - 1] or usedv[3 * N - 1] or usedv[3 * N]) {
} else {
ans = 4;
}
TateMaximumIndependentSet(g, usedv);
YokoMaximumIndependentSet(g, usedv);
TateMaximumIndependentSet2(g, usedv);
YokoMaximumIndependentSet2(g, usedv);
cout << ans << endl;
return 0;
}