QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188219 | #5485. MazeMan | ZiadElGafy# | AC ✓ | 1ms | 3812kb | C++20 | 2.6kb | 2023-09-25 16:54:31 | 2023-09-25 16:54:32 |
Judging History
answer
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define el '\n'
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef __int128 bigInt;
using namespace std;
const int N = 100 + 5, INF = 1e9 + 5, mod = 1e9 + 7, LOG = 21, SQ = 500;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
int n, m;
string a[N];
struct DSU{
int par[N * N], sz[N * N], l[N * N], d[N * N];
void init(int k){
for(int i = 0; i < k; i++) {
int r = i / m, c = i % m;
par[i] = i, sz[i] = 1;
l[i] = (a[r][c] >= 'A' and a[r][c] <= 'W');
d[i] = a[r][c] == '.';
}
}
int findPar(int v){
return (par[v] == v ? v : par[v] = findPar(par[v]));
}
void join(int u, int v){
u = findPar(u), v = findPar(v);
if(u == v)
return;
if(sz[u] < sz[v])
swap(u, v);
par[v] = u;
sz[u] += sz[v];
l[u] += l[v];
d[u] += d[v];
}
}dsu;
bool valid(int i, int j) {
return i >= 0 and i < n and j >= 0 and j < m and a[i][j] != 'X';
}
void doWork() {
cin >> n >> m;
cin.ignore();
for (int i = 0; i < n; i++) {
getline(cin, a[i]);
}
dsu.init(n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!valid(i, j)) {
continue;
}
for (int k = 0; k < 4; k++) {
int nx = i + dx[k], ny = j + dy[k];
if (valid(nx, ny)) {
if (a[i][j] >= 'A' and a[i][j] <= 'W' and a[nx][ny] >= 'A' and a[nx][ny] <= 'W') {
continue;
}
dsu.join(i * m + j, nx * m + ny);
}
}
}
}
int ans = 0, dots = 0;
unordered_set<int> vis;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!valid(i, j)) {
continue;
}
int par = dsu.findPar(i * m + j);
if (vis.find(par) != vis.end()) {
continue;
}
vis.insert(par);
int l = dsu.l[par], d = dsu.d[par];
if (l and d) {
ans++;
}
else if (d) {
dots += d;
}
}
}
cout << ans << ' ' << dots << el;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tests = 1;
// cin >> tests;
for (int i = 1; i <= tests; i++) {
doWork();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3564kb
input:
10 20 XXXXXXXAXXXXXXXBXXXX X.. ..X.X...... ...X X.XXX...X.X.XXXXXX.X X.X.XXXXX.X.X....X.X X.X... ...X.X.XX.X.X X.X.X.XXXXXXX.XX.X.X X.X.X.X...X...X....X X.X.X.XXXXXXX.XXXX.X X...X.X X.. ..X..X.X XXXXXXXDXXXXXXXXCXXX
output:
2 3
result:
ok 2 number(s): "2 3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
3 5 XDRVX X.X.X XXXXX
output:
2 0
result:
ok 2 number(s): "2 0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
3 5 NAQXX X X.X XXXXX
output:
0 1
result:
ok 2 number(s): "0 1"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
10 68 XXXXXXPXXXXXXXXCXXXXXXXXXXXXXXXXXXXXHXXXXXXXXXXXXXXIXXRXXXXXXXXXKXXX X.XX..XXXX.X.X.XXXXXX..XXXXX.X.X......X ......X.X.. X.....XXX.. X.X X X.X.XXX.. X..X..X ..X..XX.XX.XXXXX.X....X.X.X.XXXX.X. X..X.X.....X X.X..XX .XX..X....X.XX.X..XXX....X.X. .X....X.X .XX.X...X.XXX.. X..X X.X..X..XXXXXX .. ...
output:
4 116
result:
ok 2 number(s): "4 116"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
7 4 WIRX VX.S OXXN XX E K..B T.XQ CMDL
output:
2 0
result:
ok 2 number(s): "2 0"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
14 65 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X...... .XXX..X.X. ..XXX.XXX XX.X.X.XX .X.XXX..X.XX..XXXX....X .X XXX..X.XXXXXXX..X.X....XX...XXX..XXX..XX....X...X.......X..X.XXXX X.X.X......XXX .....XX. ...XX...X.X.XXX...X.....X.X.XX.XX ..X X X X...........X.....X X...XXX.XX...
output:
1 318
result:
ok 2 number(s): "1 318"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
42 20 XAXXXXXXXXXXXXXXXXNX X..X.XX.XX....XX.XXX XX.XXX X....XXX...V X......XX...XXXXX..X X....XX....X.XX....X JX.XX XXX.XX..XX.XXX X. ..XXX....XXX...XX XX.... .XXX.XX..X.XX X.X.....XX.X..X .X.X X.X. ....XX.....XX.X X X..X...X.XXXXXX..X X.......XX.X..X.XXXX X..XX...XX......XXXX XX.XX..X ...X...XX.X ...
output:
3 258
result:
ok 2 number(s): "3 258"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
45 86 XXXXXXXXXXXXXXXXXXXXXXXXXXEXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXX.X..XXXX.. XX.XX.X.X..XX....XX..X.X.X.XX.....X.X.X. ..X..XX.XX.XX.XX..X..X....XXX.X XX...XX...XXX.XX.XXXX. XX....X. XXX....XXXXX...X.X.XXX.......XXX.X..XX...X.X..X..XX.XX X XX...X.XX..XX. X...X..... .X..X...
output:
1 1791
result:
ok 2 number(s): "1 1791"
Test #9:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
35 47 XXXXXXXXXOXXXXXXXXHSXXXXXXXXNXXXXXXXXXXMXXXXXXX X.X.XXX..XXXX.....X . X........X X..XX.XX..XQ X.XXXX XX..X.....X..X....XX. XX..X..X.XX..XXX.X X.XX..X....XX.XXX. X..XXX.XX.X..X.X.X.XX.X.X..X X.X...XXX.X..X..XX X..X.. XXX..X XX.XXX..X.X..P XXX.X..X... XX.......X XX.X X...X.. ..XX.X...X X.X.XX...
output:
6 463
result:
ok 2 number(s): "6 463"
Test #10:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
68 83 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXHXXXXXXXXXXXXXXXXX X.X..XXX...X.XX.XX.......XXX .XXX .XX.......... .XXXX...XX..X.....XX.X.......X.XX.X XXX.XX. XXXX.XXXX..X..XXX..X..XXXX XX.X.X.X.......XX.XXXX.XXX.. .X....X. .X.X.XX.X X.XXXXX.. ...X.....XX.X...XX...X....XXX.XX...
output:
7 2439
result:
ok 2 number(s): "7 2439"
Test #11:
score: 0
Accepted
time: 1ms
memory: 3560kb
input:
44 49 XXXXJXIXXXXXXXXXXXXXXXXFXXXXXXXXXXXXXXXXXXXXXXXXX X.... X......X ... X.X. XXX..XXX.XX..XXXX...XX..X X.X..XXX....XXXX...X.X.X.XX. ...XXXX.X.XXX.X. .X XX...X .X..X.X. X.. .X XXXX.XX.X... X.XXXX....XXX X..X.X......X.XX.XXX.X...XXX..X .X.XX.X...XX..XXX X X XXX.X....XX..XXX.XX.XX.X.XXXXXXXXX...X.X...
output:
5 807
result:
ok 2 number(s): "5 807"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
89 61 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXLXXXXXXXXXXXXXXXXXXXXXXXX X.X X.X..X..XX.X..XXX.X.X.XXX.XXX.XX. X.X.....XX..X.XX.....XX X.X..X.XX.X.XXXXXX...X.... .XX. XXXXXXX..X...XXX..XXXX..XX.XX XXXXXX..XX.......XXXX.X...X....XX..X..X.XX.XX.XX...XXXX ..X.X X.X.XX.XX.X.. .... ..XX. .XXXX..X....X ..X.X.....
output:
8 2394
result:
ok 2 number(s): "8 2394"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
3 3 XAX X.X XXX
output:
1 0
result:
ok 2 number(s): "1 0"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
3 3 XAX X X XXX
output:
0 0
result:
ok 2 number(s): "0 0"
Test #15:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
3 3 XXX X.X XXX
output:
0 1
result:
ok 2 number(s): "0 1"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
94 5 XXXXX X..XX XXXXH X.X.X X.X.X X..XX X..XX X.. X X.X.X X.XXX L.XXX X.X.X XXX.P X...X XXXXX XXX X XX.XX X.XXX NX.XX X...X X.X.X X.XXX X..XX XXX.X XX.XX XX..X XXXXC XX..X X.XXX X..XX X..XX X...X X...X X..XX XX.XX X. XX XX..X XX..X X ..J X.. X X..XX X.XXX XXXXX X...X XX..X X.XXX Q ..X XX.XX XXXXX X...
output:
8 59
result:
ok 2 number(s): "8 59"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3496kb
input:
15 40 XXXXXXXXTXXXXXXXXXXXXXXXXXXNXXXIXXXXXKXX X.X.. .X..X.X.. ..X...XX....X.X.XX....XX XXX.......X.XXX. XXX.X....XXXX..XX.X...X X.X.X.X...X. XX.X..XX.XX.. .X.XXX..XXXXX XXX....XXXXX.XX.X.XXX.X.X.......X.XXXX.X XX.XX... XX...XX.X......X..X.X X.X.X...X XX..X.X....XXX.X.XX.XX.X...XXX.X.XXX.X.X X.X..X....
output:
7 80
result:
ok 2 number(s): "7 80"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3488kb
input:
12 100 XSXXXXXXXXXXXXXXXXXXXXXXCXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXMXXXXXXXXXXX XXXX.X..X..X.XXXX..X..XXXXXXXX....X X.XX..XXXXXXXXXXX X..XXXX.X..X....X.X ..X...XX.X..XX XX.XX..X.XX X..X X..X...X.XXX......XXX...X.X.XXX...X....X.XXXX. X... ...X.X.XX .XXXXXXXXX .X..X...X XX....
output:
1 477
result:
ok 2 number(s): "1 477"
Test #19:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
99 48 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXSCXXXXXXX XX.XX...XX..XXX.X.X.X X.. .XXX.X......XXX.X..X.X X. XX.XXX.X....X.X..XXX.XXXXXXXX.X.X..XX...X..XX X..XXXXX..XXXXX.X..X..XX..X..X..XXX.. .X...XXX.X XXX...XXXX..X..X..X..X .X.XXXX...XX.XX..XXX X.XX XX.....X.X...XXX.......X.XX....... ....XX.X..X.X ...
output:
7 1776
result:
ok 2 number(s): "7 1776"
Test #20:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
86 79 XXXXXXXXXXXXXXXXXXXXXXXXFXXXXXXXXXXXXXXCXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXPXXQXTI X.X...X.XXX. ..X.XX.X....XX. .X..X..X.X..X...X.....XX. .X.X..X.XX..X XXXXX.XXX X.XXXX....X.X...X.X. .X..............X ...X. ....X... ...X..XXX .... X..XX....A XX.X.XX.X X.XXX.XXX.XXX.XX..XX..X.X X.XXXX.XXXX.XXXXXX...
output:
7 2607
result:
ok 2 number(s): "7 2607"
Test #21:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
32 62 XXJXXXXXXXXXXXXTXXXXEXXXXXXXXXXXXXXXXXXXXXXRXCXXXXXVXXXXXXXXXX MXX...XXX.XX..X..XX.. XX.XX.XX.XX.XXX..X.XX.X.XXX..X....X...XX X........X....X.X..X.XXX..X.XX.X.XXX.XXXX...XX..XX..X.XX.X.X.X U.XXXXXXX..XXX.XXXXXXXXX.X.XXXX......X.X..XXX.. .X..X..X.XXX.X X.X X..X.XX. ..X..XXX..XXXXX..X.X..XXXXXX...
output:
11 566
result:
ok 2 number(s): "11 566"
Test #22:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
100 100 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X..................................................................................................X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
1 0
result:
ok 2 number(s): "1 0"
Test #23:
score: 0
Accepted
time: 1ms
memory: 3812kb
input:
100 100 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.XX XX.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X.X...
output:
0 4802
result:
ok 2 number(s): "0 4802"
Test #24:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
100 100 AXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXB X..................................................................................................X X............................................................................................
output:
0 9604
result:
ok 2 number(s): "0 9604"
Test #25:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
100 100 XXXXXXXXXXXXXBXXXXXXXXXXXXXXXXSXXXXXXXXXXXXXXXXFXXXXXXXXXXXXXUXXXXXXXXXXXXXXXGXXXXXXXXXXXTXXXXXXXXXA X..................................................................................................X X............................................................................................
output:
1 0
result:
ok 2 number(s): "1 0"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
100 100 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X..................................................................................................X X............................................................................................
output:
1 0
result:
ok 2 number(s): "1 0"
Test #27:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
100 100 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA A..................................................................................................A A............................................................................................
output:
1 0
result:
ok 2 number(s): "1 0"
Test #28:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
100 100 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA A A A ...
output:
0 0
result:
ok 2 number(s): "0 0"
Test #29:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
100 100 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X..................................................................................................X X............................................................................................
output:
0 9604
result:
ok 2 number(s): "0 9604"
Test #30:
score: 0
Accepted
time: 1ms
memory: 3696kb
input:
100 100 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXA AX...........................................................................................
output:
0 9216
result:
ok 2 number(s): "0 9216"
Test #31:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
5 10 ABCDEXXXXX FXXX . ..X G...XXX .X HXXX ..XXX IJKLMXXXXX
output:
3 0
result:
ok 2 number(s): "3 0"