QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54981 | #4235. Transparency | KING_UT# | AC ✓ | 20ms | 4724kb | C++20 | 2.9kb | 2022-10-11 19:59:09 | 2022-10-11 19:59:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define repn(i,b) rng(i,1,b+1)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define a first
#define b second
#define eb emplace_back
template<class t>using vc=vector<t>;
template<class t, class u>bool chmin(t &a, u b){
if(a > b){ a = b; return true;}
else return false;
}
const int inf = 100000000;
int n, p, m;
vc<int>A;
bool in[55];
vc<pair<int,char>>edge[55];
int dd[55][55];
#define mp make_pair
using P=pair<int,int>;
using Q=pair<int,pair<int,P>>;
int dist[55][55][27];
void slv(){
cin>>n>>p>>m;
rep(i,p){
int v;cin>>v;
A.pb(v);
edge[v].eb(n+1, 'a');
}
in[n+1] = 1;
rep(a,55)rep(b,55)if(a!=b)dd[a][b]=inf;
rep(i,m){
int u,v;string s;
cin>>u>>s>>v;
edge[u].eb(v, s[0]);
chmin(dd[u][v],1);
}
repn(k,n)repn(i,n)repn(j,n)chmin(dd[i][j],dd[i][k]+dd[k][j]);
auto iscap=[](char c){
return 'A'<=c and c<='Z';
};
rep(a,55)rep(c,55)rep(d,27)dist[a][c][d]=inf;
priority_queue<Q,vc<Q>,greater<Q>>que;
repn(i,n){
if(edge[i].size() < 2) continue;
rep(j, edge[i].size()){
rep(k, edge[i].size()){
if(j==k)continue;
char c = edge[i][j].b;
int to = edge[i][j].a;
char c2 = edge[i][k].b;
int to2 = edge[i][k].a;
if(iscap(c) == iscap(c2)){
if(iscap(c) and c != c2) continue;
if(chmin(dist[to][to2][26],dd[1][i]*2+2)) que.push(mp(dist[to][to2][26], mp(to,mp(to2,26))));
}
else if(iscap(c)){
if(chmin(dist[to][to2][c-'A'],dd[1][i]*2+2)) que.push(mp(dist[to][to2][c-'A'], mp(to,mp(to2,c-'A'))));
}
}
}
}
while(!que.empty()){
auto qq = que.top(); que.pop();
int cs = qq.a;
int u = qq.b.a;
int v = qq.b.b.a;
int t = qq.b.b.b;
//cout<<u<<" "<<v<<" "<<t<<" "<<cs<<endl;
if(dist[u][v][t] != cs) continue;
for(auto to:edge[v]){
int nxt = to.a;
char c = to.b;
if(!iscap(c)){
if(dist[u][nxt][t] > cs+1){
dist[u][nxt][t] = cs+1;
que.emplace(cs+1, mp(u,mp(nxt, t)));
}
}
else {
int uu, vv, tt;
if(t == 26) {
uu = nxt, vv = u, tt = c-'A';
}
else if(t == c-'A') uu=u,vv=nxt,tt=26;
else continue;
if(dist[uu][vv][tt] > cs+1){
dist[uu][vv][tt] = cs+1;
que.emplace(cs+1, mp(uu, mp(vv,tt)));
}
}
}
if(t == 26){
for(auto to:edge[u]){
int nxt = to.a;
char c = to.b;
if(!iscap(c)){
if(dist[nxt][v][t] > cs+1){
dist[nxt][v][t] = cs+1;
que.emplace(cs+1, mp(nxt,mp(v, t)));
}
}
else {
int uu, vv, tt;
{
uu = nxt,vv = v, tt = c-'A';
}
if(dist[uu][vv][tt] > cs+1){
dist[uu][vv][tt] = cs+1;
que.emplace(cs+1, mp(uu, mp(vv,tt)));
}
}
}
}
}
int ans=dist[n+1][n+1][26]-2;
if(ans > inf/2) ans = -1;
cout<<ans<<endl;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(0);
cout<<fixed<<setprecision(20);
slv();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 4068kb
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: 0ms
memory: 3896kb
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: 0ms
memory: 3980kb
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: 3896kb
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: 3884kb
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: 2ms
memory: 3896kb
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: 4060kb
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: 2ms
memory: 3896kb
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: 3972kb
input:
2 2 1 1 2 1 a 2
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3904kb
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: 0ms
memory: 3968kb
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: 3916kb
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: 3976kb
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: 0ms
memory: 4056kb
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: 20ms
memory: 4724kb
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: 2ms
memory: 4060kb
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: 11ms
memory: 4236kb
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: 3900kb
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: 2ms
memory: 3840kb
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: 1ms
memory: 3976kb
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: 3980kb
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: 0ms
memory: 4064kb
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: 4016kb
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: 3952kb
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: 15ms
memory: 4628kb
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'