QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#65183#4235. TransparencySorting#AC ✓39ms19032kbC++2.3kb2022-11-27 23:11:182022-11-27 23:11:21

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-27 23:11:21]
  • 评测
  • 测评结果：AC
  • 用时：39ms
  • 内存：19032kb
查看
  • [2022-11-27 23:11:18]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int n,k,m;
vector<pair<int,int> >e[51];
int win[51];
vector<int>adj[150001];
int d[150001];
int h(int i,int j,int k){
	return (i-1)*n*30+(j-1)*30+k;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k >> m;
	for(int i=1; i<=k ;i++){
		int x;cin >> x;win[x]=true;
	}
	for(int i=1; i<=m ;i++){
		int u,v;char c;
		cin >> u >> c >> v;
		if(c>='a' && c<='z'){
			e[u].push_back({-(c-'a'+1),v});
		}
		else{
			e[u].push_back({c-'A'+1,v});
		}
	}
	{//building edges 
		for(int i=1; i<=n ;i++){//out.k = 27,28
			adj[h(i,i,27)].push_back(h(i,i,28));
			for(auto c:e[i]){
				adj[h(i,i,28)].push_back(h(c.se,c.se,27));
				if(c.fi<0) adj[h(i,i,27)].push_back(h(c.se,i,29));
				for(auto d:e[i]){
					if(c.fi==d.fi) continue;
					if(c.fi>0 && d.fi>0) continue;
					int nk=max(c.fi,0)+max(d.fi,0);
					adj[h(i,i,28)].push_back(h(c.se,d.se,nk));
				}
			}
		}
		for(int i=1; i<=n ;i++){//out.k = 29
			for(int j=1; j<=n ;j++){
				for(auto c:e[i]){
					if(c.fi<0) adj[h(i,j,29)].push_back(h(c.se,j,29));
				}
			}
		}
		for(int i=1; i<=n ;i++){//out.k = 0
			for(int j=1; j<=n ;j++){
				for(auto c:e[i]){
					adj[h(i,j,0)].push_back(h(c.se,j,max(c.fi,0)));
				}
				for(auto c:e[j]){
					adj[h(i,j,0)].push_back(h(c.se,i,max(c.fi,0)));
				}
			}
		}
		for(int i=1; i<=n ;i++){//out.k = [1..26]
			for(int j=1; j<=n ;j++){
				for(int k=1; k<=26 ;k++){
					for(auto c:e[j]){
						if(c.fi<0) adj[h(i,j,k)].push_back(h(i,c.se,k));
						else if(c.fi==k) adj[h(i,j,k)].push_back(h(i,c.se,0));
					}
				}
			}
		}
	}
	int st=h(1,1,27);
	for(int i=1; i<=n ;i++){
		for(int j=1; j<=n ;j++){
			for(int k=0; k<30 ;k++){
				int id=h(i,j,k);
				d[id]=1e9;
			}
		}
	}
	d[st]=0;
	queue<int>q;q.push(st);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(auto c:adj[x]){
			if(d[c]>d[x]+1){
				d[c]=d[x]+1;
				q.push(c);
			}
		}
	}
	int ans=1e9;
	for(int i=1; i<=n ;i++){
		for(int j=1; j<=n ;j++){
			//cout << i << ' ' << j << ' ' << d[h(i,j,0)] << endl;
			if(!win[i] || !win[j]) continue;
			ans=min(ans,d[h(i,j,0)]);
			ans=min(ans,d[h(i,j,29)]);
		}
	}
	if(ans==1e9) cout << "-1\n";
	else cout << ans << '\n';
}
Source code, Language: C++

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

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

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

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

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

input:

1 1 1
1
1 a 1

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 5ms
memory: 6760kb

input:

1 1 1
1
1 A 1

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 5ms
memory: 6784kb

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

input:

2 2 1
1
2
1 a 2

output:

1

result:

ok single line: '1'

Test #11:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 18:43:32 | OpenSource Project