QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#118841 | #1912. Cave Paintings | bashkort# | 100 ✓ | 46ms | 21764kb | C++20 | 2.0kb | 2023-07-04 13:37:16 | 2024-05-31 18:58:53 |
Judging History
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'