QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61298#4235. TransparencyWolf_KingAC ✓7ms8240kbC++142.4kb2022-11-11 23:10:272022-11-11 23:10:30

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-11 23:10:30]
  • 评测
  • 测评结果：AC
  • 用时：7ms
  • 内存：8240kb
查看
  • [2022-11-11 23:10:27]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define per(i, a, b) for(int i = (a); i >= (b); i --)
#define Ede(i, u) for(int i = head[u]; i; i = e[i].nxt)
using namespace std;

#define eb emplace_back
typedef pair<int, int> pii;
#define mp make_pair
#define fi first
#define se second

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? - 1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

const int N = 55;
const int M = N * N * 3;
const int inf = 1e9;
int n, p, m, tr[N][60];
int tot, same[N], walk[N][N], diff[N][N];
int dis[M]; bool vis[M];
vector<pii> g[M];

void add(int u, int v, int w) {g[u].eb(mp(v, w));}

int main() {
	n = read() + 1, p = read(), m = read();
	rep(i, 1, p) {int x = read(); tr[x][0] = n;}
	rep(i, 1, m) {
		int x = read();
		char c[3]; scanf("%s", c);
		int y = read();
		int cur = (c[0] <= 'Z') ? (c[0] - 'A' + 1) : (c[0] - 'a' + 27);
		tr[x][cur] = y;
		
		if(m == 67 && i >= 35) cerr << x << ' ' << c[0] << ' ' << y << endl;
	}
	
	rep(i, 1, n) {
		same[i] = ++ tot;
		rep(j, 1, n) walk[i][j] = ++ tot, diff[i][j] = ++ tot;
	}
	
	rep(i, 1, n) {
		rep(c, 0, 52) if(tr[i][c]) add(same[i], same[tr[i][c]], 2);
		rep(c, 27, 52) if(tr[i][c]) add(same[i], walk[tr[i][c]][i], 1);
		rep(c1, 27, 52) rep(c2, 27, 52) if(tr[i][c1] && tr[i][c2] && c1 != c2)
			add(same[i], diff[tr[i][c1]][tr[i][c2]], 2);
	}
	
	rep(i, 1, n) rep(j, 1, n) {
		rep(c, 27, 52) if(tr[i][c])
			add(diff[i][j], diff[tr[i][c]][j], 1), 
			add(walk[i][j], walk[tr[i][c]][j], 1);
		rep(c, 27, 52) if(tr[j][c])
			add(diff[i][j], diff[i][tr[j][c]], 1);
		rep(c, 0, 26) if(tr[i][c] && tr[j][c])
			add(diff[i][j], diff[tr[i][c]][tr[j][c]], 2), 
			add(walk[i][j], diff[tr[i][c]][tr[j][c]], 2);
	}
	
	rep(i, 1, tot) dis[i] = inf;
	priority_queue<pii> q;
	int s = same[1]; q.push(mp(dis[s] = 0, s));
	while(! q.empty()) {
		int u = q.top().se; q.pop();
		if(vis[u]) continue; else vis[u] = true;
		for(pii e : g[u]) {
			int v = e.fi, w = e.se;
			if(dis[v] > dis[u] + w) dis[v] = dis[u] + w, q.push(mp(- dis[v], v));
		}
	}
	
	int ans = dis[diff[n][n]];
	printf("%d\n", ans == inf ? -1 : ans - 2); 
	
	cerr << (ans == inf ? -1 : ans - 2) << endl;
	
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3960kb

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: 2ms
memory: 3700kb

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: 2ms
memory: 3712kb

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: 0ms
memory: 3816kb

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: 2ms
memory: 3772kb

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: 1ms
memory: 3708kb

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: 1ms
memory: 3696kb

input:

1 1 1
1
1 a 1

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3948kb

input:

1 1 1
1
1 A 1

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

2 1 2
2
1 a 2
1 b 2

output:

2

result:

ok single line: '2'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

2 2 1
1
2
1 a 2

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3748kb

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: 2ms
memory: 3856kb

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: 4088kb

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: 3ms
memory: 4084kb

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: 7ms
memory: 4024kb

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: 5ms
memory: 8240kb

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: 4ms
memory: 8088kb

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: 4ms
memory: 8108kb

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: 2ms
memory: 3872kb

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: 0ms
memory: 3980kb

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: 2ms
memory: 3960kb

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: 1ms
memory: 3784kb

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: 2ms
memory: 3756kb

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: 0ms
memory: 3792kb

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: 2ms
memory: 3752kb

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: 0ms
memory: 8072kb

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'
English 繁體中文 简体中文

Server Time: 2024-12-04 05:58:05 | OpenSource Project