QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #208366 | #4235. Transparency | ucup-team1209# | AC ✓ | 22ms | 67216kb | C++20 | 2.9kb | 2023-10-09 14:57:18 | 2023-10-09 14:57:19 |
Judging History
answer
#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using pi = pair <int, int> ;
cs int N = 55;
int n, m, P;
bool ed[N];
vector <pi> e[N];
int id(char c) {
if('A' <= c && c <= 'Z') return c - 'A' + 1;
return c - 'a' + 27;
}
int c[N][N][N][3], nd;
cs int M = 2e6;
bool fin[M];
int d[M], ex[M];
struct dat {
int x, y, k, o;
};
vector <int> q[M];
void push(int t, int x) {
if(d[x] > t) {
d[x] = t;
q[t].pb(x);
}
}
int main() {
#ifdef zqj
freopen("1.in","r",stdin);
#endif
cin >> n >> P >> m;
for(int i = 1; i <= P; i++) {
int x;
cin >> x;
ed[x] = 1;
}
for(int i = 1; i <= m; i++) {
int x;
char c[3];
int y;
scanf("%d%s%d", & x, c, & y);
e[x].pb({y, id(c[0])});
}
vector <dat> info;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 0; k <= 26; k++)
for(int o = 0; o < 3; o++) {
c[i][j][k][o] = nd;
if(ed[i] && ed[j] && k == 0 && o) fin[nd] = 1;
info.pb({i, j, k, o});
nd ++;
}
memset(d, 0x3f, sizeof d);
q[0].pb(c[1][1][0][0]);
d[c[1][1][0][0]] = 0;
for(int t = 0; t < M; t++)
for(auto x : q[t]) {
auto [i, j, k, o] = info[x];
if(ex[x]) continue; ex[x] = 1;
if(fin[x]) {
cout << t << '\n';
return 0;
}
if(o == 2) {
assert(k == 0);
for(auto [y, c2] : e[j])
if(c2 > 26) push(t + 1, c[i][y][k][o]);
continue;
}
if(k == 0) {
if(o == 0) {
assert(i == j);
for(auto [x, c1] : e[i])
for(auto [y, c2] : e[j])
if(c1 <= 26 && c2 > 26) {
push(t + 2, c[x][y][c1][1]);
}
for(auto [x, c1] : e[i])
for(auto [y, c2] : e[j])
if(c1 > 26 && c2 > 26 && c1 != c2) {
push(t + 2, c[x][y][0][1]);
}
for(auto [x, c1] : e[i])
push(t + 2, c[x][x][0][0]);
for(auto [y, c2] : e[j])
if(c2 > 26) push(t + 1, c[i][y][k][2]);
}
for(auto [x, c1] : e[i])
for(auto [y, c2] : e[j])
if(c1 <= 26 && c2 <= 26 && c1 == c2) {
push(t + 2, c[x][y][k][o]);
}
}
else {
assert(o);
for(auto [y, c2] : e[j])
if(c2 == k) push(t + 1, c[i][y][0][o]);
}
if(o) {
for(auto [x, c1] : e[i])
if(c1 > 26) push(t + 1, c[x][j][k][o]);
for(auto [y, c2] : e[j])
if(c2 > 26) push(t + 1, c[i][y][k][o]);
}
}
cout << -1 << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 62860kb
input:
4 1 8 3 1 F 1 1 A 2 2 b 1 2 F 3 2 d 3 3 B 3 3 y 4 4 d 1
output:
10
result:
ok single line: '10'
Test #2:
score: 0
Accepted
time: 14ms
memory: 61024kb
input:
4 1 8 3 1 F 1 1 A 2 2 b 1 2 F 3 2 d 3 3 B 3 3 y 4 4 d 4
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 4ms
memory: 61480kb
input:
5 2 5 1 5 1 i 2 2 c 3 3 p 4 4 c 1 1 I 5
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 7ms
memory: 61156kb
input:
8 2 96 4 8 1 x 2 1 y 5 2 A 3 3 A 4 4 A 2 5 A 6 6 A 7 7 A 8 8 A 5 5 B 2 6 B 2 7 B 2 8 B 2 5 C 2 6 C 2 7 C 2 8 C 2 5 D 2 6 D 2 7 D 2 8 D 2 5 E 2 6 E 2 7 E 2 8 E 2 5 F 2 6 F 2 7 F 2 8 F 2 5 G 2 6 G 2 7 G 2 8 G 2 5 H 2 6 H 2 7 H 2 8 H 2 5 I 2 6 I 2 7 I 2 8 I 2 5 J 2 6 J 2 7 J 2 8 J 2 5 K 2 6 K 2 7 K 2 8...
output:
24
result:
ok single line: '24'
Test #5:
score: 0
Accepted
time: 7ms
memory: 61244kb
input:
4 1 4 1 1 d 2 2 A 3 3 A 4 4 d 1
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 61244kb
input:
7 1 8 1 1 d 2 2 A 3 3 A 4 4 d 1 1 A 5 5 d 6 6 d 7 7 A 1
output:
8
result:
ok single line: '8'
Test #7:
score: 0
Accepted
time: 3ms
memory: 60832kb
input:
1 1 1 1 1 a 1
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 7ms
memory: 61660kb
input:
1 1 1 1 1 A 1
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 5ms
memory: 60956kb
input:
2 1 2 2 1 a 2 1 b 2
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 3ms
memory: 60952kb
input:
2 2 1 1 2 1 a 2
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 4ms
memory: 61888kb
input:
4 2 3 3 4 1 A 2 2 a 3 2 b 4
output:
4
result:
ok single line: '4'
Test #12:
score: 0
Accepted
time: 4ms
memory: 66892kb
input:
50 1 149 50 1 A 2 2 B 3 3 C 4 4 D 5 5 E 6 6 F 7 7 G 8 8 H 9 9 I 10 10 J 11 11 K 12 12 L 13 13 M 14 14 N 15 15 O 16 16 P 17 17 Q 18 18 R 19 19 S 20 20 T 21 21 U 22 22 V 23 23 W 24 24 X 25 25 Y 26 26 Z 27 27 A 28 28 B 29 29 C 30 30 D 31 31 E 32 32 F 33 33 G 34 34 H 35 35 I 36 36 J 37 37 K 38 38 L 39 3...
output:
288
result:
ok single line: '288'
Test #13:
score: 0
Accepted
time: 3ms
memory: 65108kb
input:
50 1 500 50 1 A 2 1 Z 2 1 Y 2 1 X 2 1 W 2 1 V 2 1 U 2 1 T 2 1 S 2 1 R 2 2 B 3 2 A 3 2 Z 3 2 Y 3 2 X 3 2 W 3 2 V 3 2 U 3 2 T 3 2 S 3 3 C 4 3 B 4 3 A 4 3 Z 4 3 Y 4 3 X 4 3 W 4 3 V 4 3 U 4 3 T 4 4 D 5 4 C 5 4 B 5 4 A 5 4 Z 5 4 Y 5 4 X 5 4 W 5 4 V 5 4 U 5 5 E 6 5 D 6 5 C 6 5 B 6 5 A 6 5 Z 6 5 Y 6 5 X 6 ...
output:
533
result:
ok single line: '533'
Test #14:
score: 0
Accepted
time: 12ms
memory: 67152kb
input:
50 1 500 50 1 A 2 1 Z 2 1 Y 2 1 X 2 1 W 2 1 V 2 1 U 2 1 T 2 1 S 2 1 R 2 2 B 3 2 A 3 2 Z 3 2 Y 3 2 X 3 2 W 3 2 V 3 2 U 3 2 T 3 2 S 3 3 C 4 3 B 4 3 A 4 3 Z 4 3 Y 4 3 X 4 3 W 4 3 V 4 3 U 4 3 T 4 4 D 5 4 C 5 4 B 5 4 A 5 4 Z 5 4 Y 5 4 X 5 4 W 5 4 V 5 4 U 5 5 E 6 5 D 6 5 C 6 5 B 6 5 A 6 5 Z 6 5 Y 6 5 X 6 ...
output:
-1
result:
ok single line: '-1'
Test #15:
score: 0
Accepted
time: 4ms
memory: 67216kb
input:
50 2 67 2 26 1 x 3 1 w 27 2 Z 3 3 Z 4 4 Z 5 5 Z 6 6 Z 7 7 Z 8 8 Z 9 9 Z 10 10 Z 11 11 Z 12 12 Z 13 13 Z 14 14 Z 15 15 Z 16 16 Z 17 17 Z 18 18 Z 19 19 Z 20 20 Z 21 21 Z 22 22 Z 23 23 Z 24 24 Z 25 25 Z 2 26 Z 27 27 Z 28 28 Z 29 29 Z 30 30 Z 31 31 Z 32 32 Z 33 33 Z 34 34 Z 35 35 Z 36 36 Z 37 37 Z 38 38...
output:
1200
result:
ok single line: '1200'
Test #16:
score: 0
Accepted
time: 7ms
memory: 64888kb
input:
50 5 2600 12 10 36 19 9 1 A 6 1 B 12 1 C 2 1 D 35 1 E 12 1 F 50 1 G 46 1 H 13 1 I 30 1 J 24 1 K 39 1 L 21 1 M 23 1 N 46 1 O 41 1 P 5 1 Q 43 1 R 24 1 S 43 1 T 8 1 U 50 1 V 41 1 W 47 1 X 11 1 Y 4 1 Z 26 1 a 33 1 b 34 1 c 30 1 d 37 1 e 4 1 f 42 1 g 22 1 h 14 1 i 44 1 j 18 1 k 50 1 l 16 1 m 24 1 n 41 1 ...
output:
2
result:
ok single line: '2'
Test #17:
score: 0
Accepted
time: 17ms
memory: 66144kb
input:
50 20 2600 8 45 50 40 10 13 27 2 21 34 31 25 36 46 39 15 16 20 35 26 1 A 45 1 B 39 1 C 21 1 D 10 1 E 22 1 F 50 1 G 18 1 H 23 1 I 19 1 J 40 1 K 17 1 L 45 1 M 42 1 N 10 1 O 35 1 P 45 1 Q 7 1 R 6 1 S 19 1 T 40 1 U 21 1 V 39 1 W 17 1 X 30 1 Y 31 1 Z 26 1 a 18 1 b 49 1 c 18 1 d 18 1 e 29 1 f 18 1 g 49 1 ...
output:
-1
result:
ok single line: '-1'
Test #18:
score: 0
Accepted
time: 7ms
memory: 66436kb
input:
50 20 2600 8 45 50 40 10 13 27 2 21 34 31 25 36 46 39 15 16 20 35 26 1 A 45 1 B 39 1 C 21 1 D 10 1 E 22 1 F 50 1 G 18 1 H 23 1 I 19 1 J 40 1 K 17 1 L 45 1 M 42 1 N 10 1 O 35 1 P 45 1 Q 7 1 R 6 1 S 19 1 T 40 1 U 21 1 V 39 1 W 17 1 X 30 1 Y 31 1 Z 26 1 a 18 1 b 49 1 c 18 1 d 38 1 e 29 1 f 18 1 g 49 1 ...
output:
5
result:
ok single line: '5'
Test #19:
score: 0
Accepted
time: 3ms
memory: 61892kb
input:
9 2 15 6 3 1 A 2 1 f 3 2 c 4 2 H 6 2 b 5 3 G 1 4 H 4 4 e 7 4 D 1 5 d 8 5 L 3 7 F 9 8 F 9 9 H 6 9 p 1
output:
10
result:
ok single line: '10'
Test #20:
score: 0
Accepted
time: 12ms
memory: 60444kb
input:
7 3 62 5 6 7 1 A 2 2 a 5 2 b 3 2 c 4 3 a 4 3 b 4 3 c 4 3 d 4 3 e 4 3 f 4 3 g 4 3 h 4 3 i 4 3 j 4 3 k 4 3 l 4 3 m 4 3 n 4 3 o 4 3 p 4 3 q 4 3 r 4 3 s 4 3 t 4 3 u 4 3 v 4 3 w 4 3 x 4 3 y 4 3 z 4 4 a 3 4 b 3 4 c 3 4 d 3 4 e 3 4 f 3 4 g 3 4 h 3 4 i 3 4 j 3 4 k 3 4 l 3 4 m 3 4 n 3 4 o 3 4 p 3 4 q 3 4 r 3...
output:
-1
result:
ok single line: '-1'
Test #21:
score: 0
Accepted
time: 7ms
memory: 61480kb
input:
9 2 15 6 3 1 A 2 1 f 3 2 c 4 2 H 6 2 b 5 3 G 1 4 H 4 4 e 7 4 D 1 5 d 8 5 L 3 7 r 9 8 t 9 9 H 6 9 p 1
output:
7
result:
ok single line: '7'
Test #22:
score: 0
Accepted
time: 3ms
memory: 61444kb
input:
24 4 30 2 3 15 23 1 B 2 2 C 3 3 D 2 3 f 4 3 A 17 4 A 5 5 g 6 5 R 2 6 Z 7 6 N 5 7 b 8 8 g 9 9 r 10 10 h 11 10 S 10 11 T 12 12 r 13 13 K 14 14 m 15 15 L 16 16 G 1 17 x 18 18 f 19 19 Z 20 20 V 2 20 T 21 21 K 22 22 m 23 23 F 24 24 C 1
output:
23
result:
ok single line: '23'
Test #23:
score: 0
Accepted
time: 4ms
memory: 61024kb
input:
7 2 6 4 7 1 f 2 2 A 3 3 b 4 1 g 5 5 A 6 6 c 7
output:
6
result:
ok single line: '6'
Test #24:
score: 0
Accepted
time: 3ms
memory: 62516kb
input:
26 4 32 2 3 15 25 1 B 2 2 C 3 3 D 2 3 f 4 3 A 17 4 A 5 5 g 6 5 R 2 6 Z 7 6 N 5 7 b 8 8 g 9 9 r 10 10 h 11 10 S 10 11 T 12 12 r 13 13 K 14 14 m 15 15 L 16 16 G 1 17 x 18 18 f 19 19 Z 20 20 V 2 20 T 21 21 K 22 22 m 23 23 i 24 24 k 25 25 F 26 26 C 1
output:
25
result:
ok single line: '25'
Test #25:
score: 0
Accepted
time: 3ms
memory: 63020kb
input:
4 1 4 4 1 m 2 2 X 3 3 a 4 3 b 4
output:
6
result:
ok single line: '6'
Test #26:
score: 0
Accepted
time: 22ms
memory: 65060kb
input:
50 1 2600 1 1 A 35 1 B 18 1 C 24 1 D 43 1 E 9 1 F 50 1 G 5 1 H 9 1 I 6 1 J 6 1 K 26 1 L 37 1 M 48 1 N 29 1 O 18 1 P 21 1 Q 50 1 R 33 1 S 47 1 T 27 1 U 31 1 V 39 1 W 27 1 X 24 1 Y 44 1 Z 33 1 a 16 1 b 7 1 c 38 1 d 7 1 e 49 1 f 12 1 g 47 1 h 20 1 i 5 1 j 42 1 k 29 1 l 14 1 m 32 1 n 28 1 o 28 1 p 30 1 ...
output:
-1
result:
ok single line: '-1'