QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267059 | #7733. Cool, It’s Yesterday Four Times More | wuyun | WA | 1ms | 3616kb | C++20 | 3.3kb | 2023-11-26 21:52:21 | 2023-11-26 21:52:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> pa, s;
DSU(int n) : pa(n), s(n, 1) {
iota(pa.begin(), pa.end(), 0);
}
int find(int x) {
if (x != pa[x]) {
pa[x] = find(pa[x]);
}
return pa[x];
}
bool merge(int a, int b) { // b的祖先依附到a的祖先
if (joint(a, b)) return false;
s[pa[a]] += s[pa[b]];
pa[pa[b]] = pa[a];
return true;
}
bool joint(int a, int b) {
return find(a) == find(b);
}
int size(int x) {
return s[find(x)];
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<vector<char>> vec(n + 1, vector<char>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> vec[i][j];
}
}
auto getId = [&](int x, int y) {
return (x - 1) * m + y;
};
DSU dsu(n * m + 1);
vector<vector<int>> vis(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (vis[i][j] || vec[i][j] != '.') continue;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
queue<pair<int, int>> que;
que.emplace(i, j);
vis[i][j] = 1;
while (!que.empty()) {
auto [x, y] = que.front();
// cerr << x << " " << y << "x\n";
que.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
if (vis[nx][ny] || vec[nx][ny] == 'O') continue;
vis[nx][ny] = 1;
que.emplace(nx, ny);
dsu.merge(getId(i, j), getId(nx, ny));
}
}
}
}
vector<vector<pair<int, int>>> scc(n * m + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (vec[i][j] != '.') continue;
// cerr << i << " " << j << " " << dsu.find(getId(i, j)) << "\n";
scc[dsu.find(getId(i, j))].emplace_back(i, j);
}
}
vector<vector<pair<int, int>>> temp;
for (auto v : scc) {
if (v.size() != 0) {
temp.push_back(v);
}
}
swap(temp, scc);
int ans = 0;
for (int i = 0; i < (int)scc.size(); i++) {
set<pair<int, int>> st(scc[i].begin(), scc[i].end());
bool bl = true;
for (int j = 0; j < (int)scc.size() && bl; j++) {
if (i == j) continue;
int dx = scc[i][0].first - scc[j][0].first;
int dy = scc[i][0].second - scc[j][0].second;
int cnt = 0;
for (auto [x, y] : scc[j]) {
x += dx;
y += dy;
if (st.contains(pair(x, y))) {
cnt++;
}
}
if (cnt == (int)st.size()) {
bl = false;
}
}
if (bl) {
ans += (int)st.size();
}
}
cout << ans << "\n";
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO
output:
3 1 0 0
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3616kb
input:
200 2 4 OOO. OO.. 2 3 OOO .O. 3 3 O.O OOO OO. 4 1 . . O O 1 2 .O 1 1 . 2 5 .OO.. .O.O. 2 1 O O 1 1 O 1 3 .OO 5 1 O O . O . 5 2 O. .. O. .O .. 5 3 ... ... .OO ..O OOO 3 5 ..O.O .O.O. .OO.O 5 2 .O OO O. O. .. 2 1 O O 3 5 .O.OO O...O ..OO. 1 5 ..... 5 1 O . O . . 5 3 OOO OO. .OO OO. O.O 2 1 O . 5 2 O. ...
output:
3 0 0 2 1 1 5 0 0 1 0 7 9 4 4 0 6 5 2 0 1 6 4 5 2 0 0 5 3 3 1 4 1 0 7 5 2 3 9 3 0 6 2 2 2 0 4 6 6 3 5 2 5 5 2 1 0 3 3 4 4 2 2 0 7 6 4 8 5 3 2 5 2 1 2 1 4 0 0 2 5 1 4 6 9 1 6 2 2 5 4 5 2 1 0 1 9 3 4 11 0 3 2 1 0 0 4 3 1 4 3 10 3 0 3 6 2 5 1 3 3 4 0 2 11 2 2 4 0 4 4 6 2 1 2 3 0 5 0 16 4 3 2 6 0 8 3 3 ...
result:
wrong answer 7th lines differ - expected: '3', found: '5'