QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#80229 | #5485. MazeMan | chimo | WA | 5ms | 4092kb | C++ | 2.3kb | 2023-02-23 10:21:48 | 2023-02-23 10:21:52 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
const int INF = 1e9;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define re(i,a,b) for(int i=(a);i<(b);i++)
const int N = 3e2+5;
int n, m;
int c[N][N];
int dx[5] = {1,-1,0,0};
int dy[5] = {0,0,1,-1};
int getid(int x, int y) {
return y + (x-1) * m;
}
int fa[N*N], entr[N];
int getfa(int x) {
return fa[x] == x? x: fa[x]=getfa(fa[x]);
}
int vis[N*N];
int main() {
cin >> n >> m;
string s;
getline(cin, s);
rep(i,1,n) rep(j,1,m)
fa[getid(i,j)] = getid(i,j);
rep(i,1,n) {
string s;
getline(cin, s);
rep(j,1,m) c[i][j] = s[j-1];
rep(j,1,m) if (c[i][j] >= 'A' && c[i][j] <= 'W') {
entr[c[i][j]] = getid(i,j);
}
}
rep(i,1,n)rep(j,1,m) {
if (c[i][j] == 'X') continue;
int oid = getid(i,j);
rep(k,0,3) {
int ni = i+dx[k],nj = j+dy[k];
if (!(ni>=1 && ni <=n)) continue;
if (!(nj>=1 && nj <=m)) continue;
if (c[ni][nj] == 'X') continue;
if (c[i][j] >= 'A' && c[i][j] <= 'W' && c[ni][nj] >= 'A' && c[ni][nj] <='W') continue;
int nid = getid(ni,nj);
if (getfa(nid) != getfa(oid))
fa[getfa(nid)] = getfa(oid);
}
}/*
rep(i,1,n){
rep(j,1,m) cout << char(c[i][j]) << getfa(getid(i,j)) << " ";
cout << endl;
}*/
rep(i,1,n)rep(j,1,m) {
int oid = getfa(getid(i,j));
if (c[i][j] == '.') vis[oid] = 1;
}
int cntblk = 0;
map<int,int> mp;
rep(i,1,n)rep(j,1,m){
int oid = getfa(getid(i,j));
if (vis[oid]) {
vis[oid] = 0;
int gotit = false;
rep(k, 'A', 'W') if (getfa(entr[k]) == getfa(oid)) gotit = true;
if (!gotit) mp[oid] = 1; else{
cntblk ++;
//cout << i<< " " << j << " "<< char(c[i][j])<< " " << oid << endl;
}
}
}
int unreach = 0 ;
rep (i,1,n) rep(j,1,m) {
int oid = getfa(getid(i,j));
if (mp[oid] == 1 && c[i][j] == '.') unreach ++;
}
cout << cntblk << " " << unreach;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3460kb
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: 2ms
memory: 3496kb
input:
3 5 XDRVX X.X.X XXXXX
output:
2 0
result:
ok 2 number(s): "2 0"
Test #3:
score: 0
Accepted
time: 2ms
memory: 3368kb
input:
3 5 NAQXX X X.X XXXXX
output:
0 1
result:
ok 2 number(s): "0 1"
Test #4:
score: 0
Accepted
time: 2ms
memory: 3460kb
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: 2ms
memory: 3392kb
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: 3396kb
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: 2ms
memory: 3476kb
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: 0ms
memory: 3576kb
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: 2ms
memory: 3536kb
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: 3ms
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: 3ms
memory: 3564kb
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: 2ms
memory: 3772kb
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: 3356kb
input:
3 3 XAX X.X XXX
output:
1 0
result:
ok 2 number(s): "1 0"
Test #14:
score: 0
Accepted
time: 3ms
memory: 3356kb
input:
3 3 XAX X X XXX
output:
0 0
result:
ok 2 number(s): "0 0"
Test #15:
score: 0
Accepted
time: 3ms
memory: 3496kb
input:
3 3 XXX X.X XXX
output:
0 1
result:
ok 2 number(s): "0 1"
Test #16:
score: 0
Accepted
time: 3ms
memory: 3556kb
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: 1ms
memory: 3528kb
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: 1ms
memory: 3492kb
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: 3ms
memory: 3700kb
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: 3ms
memory: 3484kb
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: 4ms
memory: 3780kb
input:
100 100 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X..................................................................................................X XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
1 0
result:
ok 2 number(s): "1 0"
Test #23:
score: 0
Accepted
time: 5ms
memory: 4092kb
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: 3552kb
input:
100 100 AXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXB X..................................................................................................X X............................................................................................
output:
0 9604
result:
ok 2 number(s): "0 9604"
Test #25:
score: 0
Accepted
time: 3ms
memory: 3528kb
input:
100 100 XXXXXXXXXXXXXBXXXXXXXXXXXXXXXXSXXXXXXXXXXXXXXXXFXXXXXXXXXXXXXUXXXXXXXXXXXXXXXGXXXXXXXXXXXTXXXXXXXXXA X..................................................................................................X X............................................................................................
output:
1 0
result:
ok 2 number(s): "1 0"
Test #26:
score: 0
Accepted
time: 3ms
memory: 3608kb
input:
100 100 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX X..................................................................................................X X............................................................................................
output:
1 0
result:
ok 2 number(s): "1 0"
Test #27:
score: -100
Wrong Answer
time: 2ms
memory: 3564kb
input:
100 100 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA A..................................................................................................A A............................................................................................
output:
0 9604
result:
wrong answer 1st numbers differ - expected: '1', found: '0'