QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363305 | #8507. Clever Cell Choices | ucup-team3215# | WA | 0ms | 3892kb | C++20 | 1.4kb | 2024-03-23 20:54:42 | 2024-03-23 20:54:43 |
Judging History
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 (w == -1) W = 1;
s += t;
});
if (W) return {1};
s = 1 - s;
if (tup[v] > tin[p]) if (s <= 0) return {1}; else return {-1};
return {0, 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 << i / N << ' ' << i % N << '\n';
}
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
3 3 #.# ... #.#
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 3 ..# ... ...
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 4 ...#
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
1 5 ####.
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3816kb
input:
1 6 #..###
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 5 ....# ###.#
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
2 6 ...##. .#.###
output:
4
result:
ok 1 number(s): "4"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
5 5 ##... ##.#. ##.## ##.#. .##..
output:
7
result:
ok 1 number(s): "7"
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3516kb
input:
6 6 ...##. #..#.. ...... ..#... #...## .#....
output:
4
result:
wrong answer 1st numbers differ - expected: '1', found: '4'