QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #258759 | #4235. Transparency | chen_zexing | AC ✓ | 7ms | 7576kb | C++17 | 10.0kb | 2023-11-20 05:42:38 | 2023-11-20 05:42:38 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int nxt[55][130];
int dp[55][55][2][2][53];
int f[55];
struct node{
int x,y,f,l,c;
};
int sp[55][55];
int main() {
int T = 1, kase = 0;
//cin >> T;
while (T--) {
int n,p,t;
cin>>n>>p>>t;
memset(dp,-1,sizeof(dp));
for(int i=1,x;i<=p;i++) scanf("%d",&x),f[x]=1;
for(int i=1,x,y;i<=t;i++){
scanf("%d",&x);
char c='?';
while((c<'a'||c>'z')&&(c<'A'||c>'Z')) scanf("%c",&c);
scanf("%d",&y);
nxt[x][c]=y;
}
dp[1][1][0][0][0]=0;
queue <node> q;
q.push(node{1,1,0,0,0});
while(!q.empty()){
auto temp=q.front();
q.pop();
int x=temp.x,y=temp.y,c=temp.c,l=temp.l,f=temp.f,d=dp[x][y][f][l][c];
//cout<<x<<" "<<y<<" "<<f<<" "<<l<<" "<<c<<" "<<d<<endl;
assert(d!=-1);
if(!f){
if(!c){
for(int i=0;i<26;i++) {
if (nxt[x][i + 'a']) {
if (dp[nxt[x][i + 'a']][y][f][0][i + 27] == -1) {
dp[nxt[x][i + 'a']][y][f][0][i + 27] = d + 1;
q.push(node{nxt[x][i + 'a'], y, f, 0, i + 27});
}
}
if (nxt[x][i + 'A']) {
if (dp[nxt[x][i + 'A']][y][f][0][i + 1] == -1) {
dp[nxt[x][i + 'A']][y][f][0][i + 1] = d + 1;
q.push(node{nxt[x][i + 'A'], y, f, 0, i + 1});
}
}
if (nxt[y][i + 'a']) {
if (dp[x][nxt[y][i+'a']][f][1][i + 27] == -1) {
dp[x][nxt[y][i+'a']][f][1][i + 27] = d + 1;
q.push(node{x, nxt[y][i+'a'], f, 1, i + 27});
}
}
if (nxt[y][i + 'A']) {
if (dp[x][nxt[y][i+'A']][f][1][i + 1] == -1) {
dp[x][nxt[y][i+'A']][f][1][i + 1] = d + 1;
q.push(node{x, nxt[y][i+'A'], f, 1, i + 1});
}
}
}
}
else if(c>26){
if(l==0){
for(int i=0;i<26;i++){
if(nxt[y][i+'a']){
int type=i!=c-27;
if(dp[x][nxt[y][i+'a']][type][0][0]==-1){
dp[x][nxt[y][i+'a']][type][0][0]=d+1;
q.push(node{x,nxt[y][i+'a'],type,0,0});
}
}
if(nxt[y][i+'A']){
if(dp[x][nxt[y][i+'A']][1][1][i+1]==-1){
dp[x][nxt[y][i+'A']][1][1][i+1]=d+1;
q.push(node{x,nxt[y][i+'A'],1,1,i+1});
}
}
}
}
else{
for(int i=0;i<26;i++){
if(nxt[x][i+'a']){
int type=i!=c-27;
if(dp[nxt[x][i+'a']][y][type][0][0]==-1){
dp[nxt[x][i+'a']][y][type][0][0]=d+1;
q.push(node{nxt[x][i+'a'],y,type,0,0});
}
}
if(nxt[x][i+'A']){
if(dp[nxt[x][i+'A']][y][1][0][i+1]==-1){
dp[nxt[x][i+'A']][y][1][0][i+1]=d+1;
q.push(node{nxt[x][i+'A'],y,1,0,i+1});
}
}
}
}
}
else{
if(l==0){
for(int i=0;i<26;i++)
if(nxt[y][i+'a']){
if(dp[x][nxt[y][i+'a']][1][0][c]==-1){
dp[x][nxt[y][i+'a']][1][0][c]=d+1;
q.push(node{x,nxt[y][i+'a'],1,0,c});
}
}
if(nxt[y][c-1+'A']){
if(dp[x][nxt[y][c-1+'A']][0][0][0]==-1){
dp[x][nxt[y][c-1+'A']][0][0][0]=d+1;
q.push(node{x,nxt[y][c-1+'A'],0,0,0});
}
}
}
else{
for(int i=0;i<26;i++)
if(nxt[x][i+'a']){
if(dp[nxt[x][i+'a']][y][1][1][c]==-1){
dp[nxt[x][i+'a']][y][1][1][c]=d+1;
q.push(node{nxt[x][i+'a'],y,1,1,c});
}
}
if(nxt[x][c-1+'A']){
if(dp[nxt[x][c-1+'A']][y][0][0][0]==-1){
dp[nxt[x][c-1+'A']][y][0][0][0]=d+1;
q.push(node{nxt[x][c-1+'A'],y,0,0,0});
}
}
}
}
}
else{
assert(c<=26);
if(c==0){
for(int i=0;i<26;i++){
if (nxt[x][i + 'a']) {
if (dp[nxt[x][i + 'a']][y][f][0][0] == -1) {
dp[nxt[x][i + 'a']][y][f][0][0] = d + 1;
q.push(node{nxt[x][i + 'a'], y, f, 0, 0});
}
}
if (nxt[x][i + 'A']) {
if (dp[nxt[x][i + 'A']][y][f][0][i + 1] == -1) {
dp[nxt[x][i + 'A']][y][f][0][i + 1] = d + 1;
q.push(node{nxt[x][i + 'A'], y, f, 0, i + 1});
}
}
if (nxt[y][i + 'a']) {
if (dp[x][nxt[y][i+'a']][f][1][0] == -1) {
dp[x][nxt[y][i+'a']][f][1][0] = d + 1;
q.push(node{x, nxt[y][i+'a'], f, 1,0});
}
}
if (nxt[y][i + 'A']) {
if (dp[x][nxt[y][i+'A']][f][1][i + 1] == -1) {
dp[x][nxt[y][i+'A']][f][1][i + 1] = d + 1;
q.push(node{x, nxt[y][i+'A'], f, 1, i + 1});
}
}
}
}
else{
if(l==0){
for(int i=0;i<26;i++)
if(nxt[y][i+'a']){
if(dp[x][nxt[y][i+'a']][1][0][c]==-1){
dp[x][nxt[y][i+'a']][1][0][c]=d+1;
q.push(node{x,nxt[y][i+'a'],1,0,c});
}
}
if(nxt[y][c-1+'A']){
if(dp[x][nxt[y][c-1+'A']][1][0][0]==-1){
dp[x][nxt[y][c-1+'A']][1][0][0]=d+1;
q.push(node{x,nxt[y][c-1+'A'],1,0,0});
}
}
}
else{
for(int i=0;i<26;i++)
if(nxt[x][i+'a']){
if(dp[nxt[x][i+'a']][y][1][1][c]==-1){
dp[nxt[x][i+'a']][y][1][1][c]=d+1;
q.push(node{nxt[x][i+'a'],y,1,1,c});
}
}
if(nxt[x][c-1+'A']){
if(dp[nxt[x][c-1+'A']][y][1][0][0]==-1){
dp[nxt[x][c-1+'A']][y][1][0][0]=d+1;
q.push(node{nxt[x][c-1+'A'],y,1,0,0});
}
}
}
}
}
}
int ans=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(f[i]&&f[j]&&dp[i][j][1][0][0]!=-1){
//cout<<i<<" "<<j<<" "<<dp[i][j][1][0][0]<<endl;
if(ans==-1) ans=dp[i][j][1][0][0];
else ans=min(ans,dp[i][j][1][0][0]);
}
memset(sp,-1,sizeof(sp));
queue <pair<int,int>> spq;
for(int i=1;i<=n;i++) spq.push({i,i}),sp[i][i]=0;
while(!spq.empty()){
auto temp=spq.front();
spq.pop();
int x=temp.first,y=temp.second,d=sp[x][y];
//cout<<x<<" "<<y<<" "<<d<<endl;
for(int i=0;i<26;i++)
if(nxt[y][i+'a']){
if(sp[x][nxt[y][i+'a']]<=0){
sp[x][nxt[y][i+'a']]=d+1;
spq.push({x,nxt[y][i+'a']});
}
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(f[i]&&f[k]&&dp[i][j][0][0][0]!=-1&&sp[j][k]>0){
if(ans==-1) ans=dp[i][j][0][0][0]+sp[j][k];
else ans=min(ans,dp[i][j][0][0][0]+sp[j][k]);
}
printf("%d\n",ans);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6584kb
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: 1ms
memory: 6320kb
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: 1ms
memory: 6296kb
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: 1ms
memory: 6588kb
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: 1ms
memory: 6292kb
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: 6300kb
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: 0ms
memory: 6292kb
input:
1 1 1 1 1 a 1
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 1ms
memory: 6296kb
input:
1 1 1 1 1 A 1
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 6296kb
input:
2 1 2 2 1 a 2 1 b 2
output:
2
result:
ok single line: '2'
Test #10:
score: 0
Accepted
time: 1ms
memory: 6308kb
input:
2 2 1 1 2 1 a 2
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 0ms
memory: 6576kb
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: 1ms
memory: 6572kb
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: 0ms
memory: 6328kb
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: 6312kb
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: 1ms
memory: 6344kb
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: 7576kb
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: 0ms
memory: 6520kb
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: 6ms
memory: 6992kb
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: 1ms
memory: 6552kb
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: 6308kb
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: 6304kb
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: 6596kb
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: 1ms
memory: 6300kb
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: 1ms
memory: 6304kb
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: 0ms
memory: 6296kb
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: 7ms
memory: 7516kb
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'