QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397207 | #8114. Labirint | lfxxx# | 0 | 3ms | 4588kb | C++14 | 1.8kb | 2024-04-23 19:41:59 | 2024-07-04 03:37:05 |
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 105;
int n, m, a[N][N], b[N][N];
struct dsu {
int fa[N * N];
dsu() {
iota(fa, fa + N, 0);
}
int find(int k)
{
return fa[k] == k ? k : fa[k] = find(fa[k]);
}
void merge(int u, int v)
{
u = find(u), v = find(v);
if (u == v) return;
fa[u] = v;
}
}d[16];
int to(char c)
{
if (c == 'P') return 0;
if (c == 'C') return 1;
if (c == 'Z') return 2;
return 3;
}
int id(int i, int j)
{
return (i - 1) * m + j;
}
bool en;
int main()
{
#ifdef IAKIOI
freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
cerr << (&be - &en) / 1024.0 / 1024 << " MB\n-------------------\n";
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
char c;
cin >> c;
a[i][j] = to(c);
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
char c;
cin >> c;
b[i][j] = to(c);
}
}
for (int S = 0; S < 16; ++S) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
if ((S >> a[i][j]) & 1) {
d[S].merge(id(i, j), id(i, j + 1));
}
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
if ((S >> b[i][j]) & 1) {
d[S].merge(id(i, j), id(i + 1, j));
}
}
}
}
int q;
cin >> q;
while (q--) {
int a, b, c, D;
cin >> a >> b >> c >> D;
int x = id(a, b), y = id(c, D), ans = 5;
cout << x << ' ' << y << '\n';
for (int S = 0; S < 16; ++S) {
if (d[S].find(x) == d[S].find(y)) {
ans = min(ans, __builtin_popcount(S));
}
}
cout << ans << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3672kb
input:
1 100 NPPPZNNPCPCNZNZNZPZZPPPNPCPNPZCPCPCNNCZZPPCPPZPNPNCZCPZNZNPPZNPPZZNPPNCNPZZPZPZZNPCPNNZNNPCNCPZPCNN 100 1 55 1 37 1 52 1 64 1 36 1 4 1 68 1 66 1 50 1 80 1 84 1 77 1 99 1 68 1 84 1 56 1 5 1 95 1 38 1 68 1 82 1 3 1 64 1 36 1 61 1 21 1 1 1 4 1 2 1 46 1 55 1 100 1 4 1 83 1 53 1 96 1 76 1 43 1 21 1...
output:
55 37 4 52 64 4 36 4 4 68 66 2 50 80 4 84 77 4 99 68 4 84 56 4 5 95 4 38 68 4 82 3 4 64 36 4 61 21 4 1 4 2 2 46 4 55 100 4 4 83 4 53 96 4 76 43 4 21 19 1 77 45 4 37 84 4 17 69 4 65 50 4 64 61 3 25 78 4 96 1 4 83 35 4 3 1 2 11 48 4 64 37 4 97 59 4 52 91 4 66 50 4 31 15 4 10 56 4 93 40 4 48 15 4 89 54...
result:
wrong answer 1st lines differ - expected: '4', found: '55 37'
Subtask #2:
score: 0
Wrong Answer
Test #7:
score: 0
Wrong Answer
time: 2ms
memory: 4588kb
input:
100 100 PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP...
output:
9826 7630 0 104 1050 1 135 1637 0 8394 3300 0 7853 828 0 2384 2339 0 6880 9357 0 5090 2240 0 1199 3698 0 7636 7977 0 1977 5423 0 6195 3116 0 3521 3025 0 6089 6100 0 1781 9773 0 9371 7860 0 3874 9105 0 9359 844 0 797 3957 0 6981 9139 0 5023 7814 0 4960 7321 0 973 6760 0 9506 2425 0 7349 359 0 8928 53...
result:
wrong answer 1st lines differ - expected: '2', found: '9826 7630'
Subtask #3:
score: 0
Wrong Answer
Test #16:
score: 0
Wrong Answer
time: 3ms
memory: 4588kb
input:
100 100 PPPPCCCCCCCCCPCCPPCCCPPPCCPPCCCPPPPPCCCCCCCPCCCPCCPPCCCPPCCCPPPCPPPPPPCCPPPCCCPPCCCCCPPPPPPPPCPPCPC PCPCPCCCCCCCPPPCCPPPPPPCPPPCPCPCCPPPCPCPCCPCCCCCCPPPCCPCCPCPCCPPCPPCCPCCPPPCPPPCPPCPCPPPCPCPPCPCCCC PCPCCCPPCPPPPCCCCCPCPPCCPPPPPCCCPCPPPPPPPCCPPCCPPCCPCCCCCPPCCCPPCPCPPCCPCPCPCPPPPCCPPPPCCPCP...
output:
1792 8083 0 6952 9359 0 7801 2619 0 3261 1366 0 5290 4547 0 9050 9441 0 3997 5062 0 413 8417 0 6330 7439 0 8039 5388 0 3191 3920 0 950 8282 0 1211 8837 0 8265 7314 0 6547 2373 0 518 5095 0 9674 2836 0 7625 8035 0 5888 2853 0 3711 8978 0 2369 8471 0 9737 4868 0 9359 3329 0 2786 3886 0 5342 4944 0 917...
result:
wrong answer 1st lines differ - expected: '2', found: '1792 8083'
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 3ms
memory: 4396kb
input:
100 100 PZCZZZNPZPZPCCCCPNPZCCZZPPPPNCPZNPZPPNZNCPCNPCNCZZNCCZPZPPPZZZCZCZNPZPNZZZPPZPPZZPCPCZPNNCZZCPCNNNZ NCZZPPCZNZNNNNNNPPNNCPZCZNNPNCCPZZZCZNPZZZNCCNNZPPCPZNPCPCZCZPZCCPPPCZPZCCPNNNNZZZZCZZNZNZPPZPCNZPC PCCNZCCZZPZPPNZZNPCCNNZPCNPPZZNCPZNZPCZZPPCCCCNNZZCCNPPZNZNZZZNNNNZZNCNCCCNZPCZCPPZPCPCPZNPP...
output:
6397 3901 0 8536 4633 0 8654 6887 0 5930 7996 0 2684 9204 0 2351 4320 0 3123 4548 0 9207 3356 0 4096 1622 0 3754 4258 0 6952 3777 0 8022 285 0 8451 4316 0 9265 5923 0 2326 4037 0 2473 7975 0 5899 983 0 2889 1182 0 6971 4089 0 5497 8399 0 604 9358 0 7992 4339 0 5134 8474 0 5046 5992 0 6288 6070 0 560...
result:
wrong answer 1st lines differ - expected: '3', found: '6397 3901'