QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363289#8507. Clever Cell Choicesucup-team3215#WA 1ms3852kbC++201.4kb2024-03-23 20:37:552024-03-23 20:37:55

Judging History

你现在查看的是最新测评结果

  • [2024-03-23 20:37:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3852kb
  • [2024-03-23 20:37:55]
  • 提交

answer

#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

constexpr int N = 52;

bool a[N * N];

int tin[N * N], tup[N * N], ct;

void iternei(int v, auto f) {
  for (auto di: {-1, 0, 1})
  for (auto dj: {-1, 0, 1}) if (!di ^ !dj) if (a[v + di * N + dj]) f(v + di * N + dj);
}

void calct(int v, int p) {
  tin[v] = ++ct;
  tup[v] = ct + 1;
  iternei(v, [&](int u) {
    if (u == p) return;
    else if (tin[u]) tup[v] = min(tup[v], tin[u]);
    else calct(u, v), tup[v] = min(tup[v], tup[u]);
  });
}

array<int, 2> solve(int v, int p) {
  bool W = 0;
  int s = 0;
  iternei(v, [&](int u) {
    if (tin[u] < tin[v]) return;
    auto [w, t] = solve(u, v);
    if (tup[u] > tin[v] && w == -1 || tup[v] > tin[p] && t > 0) W = 1;
    s += t;
  });
  if (W) return {1};
  if (tup[v] > tin[p]) return {-1, 0};
  return {0, 1 - s};
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m; cin >> n >> m;
  vector<string> v(n);
  for (auto& s: v) cin >> s;
  for (int i = 0; i < n; ++i)
  for (int j = 0; j < m; ++j) if (v[i][j] == '.') a[i * N + j + N + 1] = 1;
  int ans = 0;
  for (int i = 0; i < N * N; ++i) if (a[i]) {
    fill(tin, end(tin), ct = 0);
    calct(i, i);
    auto [w, t] = solve(i, i);
    if (w == 1 || w != -1 && t <= 0) continue;
    ++ans;
  }
  cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3848kb

input:

3 3
#.#
...
#.#

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3576kb

input:

3 3
..#
...
...

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3500kb

input:

1 4
...#

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

1 5
####.

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 3604kb

input:

1 6
#..###

output:

0

result:

ok 1 number(s): "0"

Test #6:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

2 5
....#
###.#

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

2 6
...##.
.#.###

output:

4

result:

ok 1 number(s): "4"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

5 5
##...
##.#.
##.##
##.#.
.##..

output:

7

result:

ok 1 number(s): "7"

Test #9:

score: -100
Wrong Answer
time: 1ms
memory: 3596kb

input:

6 6
...##.
#..#..
......
..#...
#...##
.#....

output:

4

result:

wrong answer 1st numbers differ - expected: '1', found: '4'