QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#847148 | #5730. Maze Connect | Yarema# | AC ✓ | 69ms | 14644kb | C++20 | 2.3kb | 2025-01-07 18:02:34 | 2025-01-07 18:02:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef double db;
struct DSU
{
int n;
VI p, sz;
DSU(int _n = 0)
{
n = _n;
p.resize(n);
iota(ALL(p), 0);
sz.assign(n, 1);
}
int find(int v)
{
if (v == p[v])
return v;
return p[v] = find(p[v]);
}
bool unite(int u, int v)
{
u = find(u);
v = find(v);
if (u == v)
return false;
if (sz[u] > sz[v])
swap(u, v);
p[u] = v;
sz[v] += sz[u];
return true;
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
DSU d(n * m);
vector<string> v(n);
FOR (i, 0, n)
cin >> v[i];
int ans = 0;
FOR (i, 0, n)
{
FOR (j, 0, m)
{
if (i + 1 < n && j + 1 < m &&
v[i][j] == '/' && v[i][j + 1] == '\\' &&
v[i + 1][j] == '\\' && v[i + 1][j + 1] == '/')
ans++;
if (v[i][j] != '.')
continue;
FOR (dx, -1, 2)
{
FOR (dy, -1, 2)
{
int ni = i + dx;
int nj = j + dy;
if (0 <= ni && ni < n && 0 <= nj && nj < m &&
v[ni][nj] == '.' && abs(dx) + abs(dy) == 1)
d.unite(i * m + j, ni * m + nj);
}
}
if (i > 0 && j > 0 && v[i - 1][j - 1] == '.' && v[i - 1][j] != '/')
d.unite(i * m + j, i * m + j - m - 1);
if (i > 0 && j + 1 < m && v[i - 1][j + 1] == '.' && v[i - 1][j] != '\\')
d.unite(i * m + j, i * m + j - m + 1);
if (i + 1 < n && j > 0 && v[i + 1][j - 1] == '.' && v[i + 1][j] != '\\')
d.unite(i * m + j, i * m + j + m - 1);
if (i + 1 < n && j + 1 < m && v[i + 1][j + 1] == '.' && v[i + 1][j] != '/')
d.unite(i * m + j, i * m + j + m + 1);
}
}
set<int> border;
set<int> comps;
FOR (i, 0, n)
{
FOR (j, 0, m)
{
if ((i == 0 || j == 0 || i + 1 == n || j + 1 == m) && v[i][j] == '.')
border.insert(d.find(i * m + j));
if (v[i][j] == '.')
comps.insert(d.find(i * m + j));
}
}
cout << ans + SZ(comps) - SZ(border) << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
input:
2 2 /\ \/
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
4 4 /\.. \.\. .\/\ ..\/
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
2 2 \/ /\
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
8 20 /\/\/\/\/\/\/\/\/\/\ \../\.\/./././\/\/\/ /./\.././\/\.\/\/\/\ \/\/\.\/\/./\/..\../ /\/./\/\/./..\/\/..\ \.\.././\.\/\/./\.\/ /.../\../..\/./.../\ \/\/\/\/\/\/\/\/\/\/
output:
26
result:
ok single line: '26'
Test #5:
score: 0
Accepted
time: 6ms
memory: 12092kb
input:
1000 1000 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
499001
result:
ok single line: '499001'
Test #6:
score: 0
Accepted
time: 3ms
memory: 12136kb
input:
1000 1000 \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...
output:
499000
result:
ok single line: '499000'
Test #7:
score: 0
Accepted
time: 69ms
memory: 14644kb
input:
1000 1000 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
122943
result:
ok single line: '122943'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
100 100 ................................................./\................................................. ................................................/..\................................................ .............................................../....\........................................
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
100 100 ................................................./\................................................. ................................................/..\................................................ ..............................................././\.\........................................
output:
25
result:
ok single line: '25'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
40 40 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\...
output:
760
result:
ok single line: '760'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
40 40 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\...
output:
760
result:
ok single line: '760'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
21 21 /\/\/\/\/\/\/\/\/\/\. \...\...\...\...\...\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\....
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 19ms
memory: 11988kb
input:
997 997 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
10 10 ..../\.... .../..\... .././\.\.. ././..\.\. /././\.\.\ \.\.\/././ .\.\.././. ..\.\/./.. ...\../... ....\/....
output:
3
result:
ok single line: '3'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
10 11 ...../\.... ..../..\... ..././\.\.. .././..\.\. ./././\.\.\ .\.\.\/././ ..\.\.././. ...\.\/./.. ....\../... .....\/....
output:
3
result:
ok single line: '3'
Test #16:
score: 0
Accepted
time: 53ms
memory: 11932kb
input:
1000 1000 .....................................................................................................................................................................................................................................................................................................
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
100 100 ././././././././././././././././././././././././././././././././././././././././././././././././././ /./././././././././././././././././././././././././././././././././././././././././././././././././. ./././././././././././././././././././././././././././././././././././././././././././././...
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
100 100 .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\ \.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\. .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\...
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
100 100 .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\ ././././././././././././././././././././././././././././././././././././././././././././././././././ .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\...
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
4 4 /\/\ \/\/ /\/\ \/\/
output:
5
result:
ok single line: '5'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
3 3 /\. \/\ .\/
output:
2
result:
ok single line: '2'
Test #22:
score: 0
Accepted
time: 52ms
memory: 11876kb
input:
1000 1000 \/..\../..\/\/./......./..././..\../.../....\.\/././......./././.../..........\...\/.../..\.\../......\.....\.\/..\.././..\...\/...../.../\/./..\.......\../..\/\/..\/...../..././\/./..././................\....../..\....../././.../....\...\/....\.\/......\.......\../.../....\.\/..\....../.....
output:
86
result:
ok single line: '86'
Test #23:
score: 0
Accepted
time: 26ms
memory: 7628kb
input:
1000 500 /\.\...\/\...././....././\.\.....\.\/././\../......\...\.\.......\/././....\.././......./.../.../\.........\/....\../..\.....\........../\/\.....\/......./..\/......./........\.....\...\...\/./...../..\/......\..../.........../..\.\...././..........\/././\......../\/........\....../\...\../...
output:
722
result:
ok single line: '722'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
100 100 \/\/\/\/\/.../.../\/\.\/\.\/\/.../././\.\../././\........../..\/..././.../..\.\.......\/\..../\..../ /./\/\.\/...../.../\..../\../..\/.../..././.../..\...\../\/\.\../\/././..\/...../....././....\/././\ \/\.\...\/....\/.../......\/\.\.\...\/..\.\/\/..\../..\...\/\/\/./\../....\/\/./.../\/\../...
output:
184
result:
ok single line: '184'
Test #25:
score: 0
Accepted
time: 4ms
memory: 3704kb
input:
250 250 /\............/..\........../.../....././\....../....\.....\............................../.../.../..........\...\....../....\...\/........\.\/./...../..........\..../............\..../....\...\.......././....\.\................../...../..\.\/..\.\/\ ..\...\/...../\...\.......\.\.\/./\.\/......
output:
6
result:
ok single line: '6'
Test #26:
score: 0
Accepted
time: 27ms
memory: 7692kb
input:
500 1000 /\.\/\../....\/\.\/..././.../\/....\.././\/..\.\/..\/..\...\...\/....././....\.\.\.\.\.././\/./..\/.../..\/..\.\/./....\/./..\...\/..\/.../\..../..\/..\.\.\.....\/.../..\.\...\.\/........\/./..\...\/./...../\.\/././....\/..\/./\.\.\/././\/..\/./.../\...././..\/././...../\/\../..\/./\../.......
output:
2762
result:
ok single line: '2762'
Test #27:
score: 0
Accepted
time: 15ms
memory: 5456kb
input:
500 500 \...\../..\...\/...../\....../..\.....././....\/.../........\...\...\/./.../..././.../......\../\/....\...\../..\...\/..........\.././...../...../..\...\...\..../..\.\.....\/............\...\/\/..\.............\....../\/.../././\.....././.../............\..../\/./..\.\......../..\.....\../.....
output:
663
result:
ok single line: '663'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
50 50 /\.\.\.\.././.../..././.../\.....\/..\/\.\...\.... ...../\.....\.\/./\/......./\..../..\/..\.\/./\../ ..../\.\/\..../..\.\../........\/....\.././\...\/\ \/\/././\...\/./\/........\.....\/\/./..\...\/\... ...\/...../\.........\/..\.\...\/.../.../\../..\.. \../....\../..\.././././\.\../...../......
output:
21
result:
ok single line: '21'