QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#118841#1912. Cave Paintingsbashkort#100 ✓46ms21764kbC++202.0kb2023-07-04 13:37:162024-05-31 18:58:53

Judging History

This is the latest submission verdict.

  • [2024-05-31 18:58:53]
  • Judged
  • Verdict: 100
  • Time: 46ms
  • Memory: 21764kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-04 13:37:16]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 1e6, MOD = 1e9 + 7;

int fa[N], mxi[N], dp[N];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) {
        return false;
    }
    dp[x] = 1LL * dp[x] * dp[y] % MOD;
    fa[y] = x;
    mxi[x] = max(mxi[x], mxi[y]);
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    iota(fa, fa + N, 0);
    fill(dp, dp + N, 1);
    vector<string> s(n);

    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            mxi[i * m + j] = i;
        }
    }

    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < m; ++j) {
            if (s[i][j] == '.') {
                if (i + 1 < n && s[i + 1][j] == '.') {
                    unite(i * m + j, (i + 1) * m + j);
                }
                if (j + 1 < m && s[i][j + 1] == '.') {
                    unite(i * m + j, i * m + j + 1);
                }
            }
        }

        vector<int> h;

        for (int j = 0; j < m; ++j) {
            if (s[i][j] == '.') {
                h.push_back(find(i * m + j));
            }
        }

        sort(h.begin(), h.end());
        h.resize(unique(h.begin(), h.end()) - h.begin());

        for (int x : h) {
            if (++dp[x] == MOD) {
                dp[x] = 0;
            }
        }
    }

    int ans = 1;

    vector<int> h;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (s[i][j] == '.') {
                h.push_back(find(i * m + j));
            }
        }
    }

    sort(h.begin(), h.end());
    h.resize(unique(h.begin(), h.end()) - h.begin());

    for (int x : h) {
        ans = 1LL * ans * dp[x] % MOD;
    }

    cout << ans << '\n';

    return 0;
}

詳細信息

Test #1:

score: 6.66667
Accepted
time: 3ms
memory: 13288kb

input:

4 9
#########
#...#...#
#.#...#.#
#########

output:

9

result:

ok single line: '9'

Test #2:

score: 6.66667
Accepted
time: 41ms
memory: 21408kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

698252557

result:

ok single line: '698252557'

Test #3:

score: 6.66667
Accepted
time: 46ms
memory: 18224kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

457114634

result:

ok single line: '457114634'

Test #4:

score: 6.66667
Accepted
time: 41ms
memory: 18200kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

668532341

result:

ok single line: '668532341'

Test #5:

score: 6.66667
Accepted
time: 41ms
memory: 18088kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

195420699

result:

ok single line: '195420699'

Test #6:

score: 6.66667
Accepted
time: 37ms
memory: 18056kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

656707057

result:

ok single line: '656707057'

Test #7:

score: 6.66667
Accepted
time: 11ms
memory: 16720kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

119617636

result:

ok single line: '119617636'

Test #8:

score: 6.66667
Accepted
time: 3ms
memory: 13312kb

input:

10 10
##########
#.##...###
#.#.#..###
#.#.....##
#......#.#
#..###.#.#
#####..###
##...###.#
#####..#.#
##########

output:

360

result:

ok single line: '360'

Test #9:

score: 6.66667
Accepted
time: 3ms
memory: 13448kb

input:

10 10
##########
#..#..#..#
#.#..##..#
#.#.##.###
#...##..##
##...#.###
#..#####.#
#...#.##.#
#####.#.##
##########

output:

1728

result:

ok single line: '1728'

Test #10:

score: 6.66667
Accepted
time: 3ms
memory: 13224kb

input:

10 10
##########
##.###.#.#
#...####.#
##..#.####
##....#..#
#.###.#.##
##...###.#
##.#######
##.##...##
##########

output:

3456

result:

ok single line: '3456'

Test #11:

score: 6.66667
Accepted
time: 0ms
memory: 13164kb

input:

10 10
##########
#.##..####
###.###.##
#...###..#
#.#....###
##########
####..####
######.###
#.##.#.#.#
##########

output:

3456

result:

ok single line: '3456'

Test #12:

score: 6.66667
Accepted
time: 33ms
memory: 21336kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

22389053

result:

ok single line: '22389053'

Test #13:

score: 6.66667
Accepted
time: 31ms
memory: 20336kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

664371911

result:

ok single line: '664371911'

Test #14:

score: 6.66667
Accepted
time: 40ms
memory: 21380kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

534672947

result:

ok single line: '534672947'

Test #15:

score: 6.66667
Accepted
time: 45ms
memory: 21764kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

377322628

result:

ok single line: '377322628'