QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267059#7733. Cool, It’s Yesterday Four Times MorewuyunWA 1ms3616kbC++203.3kb2023-11-26 21:52:212023-11-26 21:52:21

Judging History

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

  • [2023-11-26 21:52:21]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3616kb
  • [2023-11-26 21:52:21]
  • 提交

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'