QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#314014#1193. Ambiguous Encoding11d10xyWA 1ms4632kbC++141.0kb2024-01-25 11:15:042024-01-25 11:15:06

Judging History

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

  • [2024-01-25 11:15:06]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4632kb
  • [2024-01-25 11:15:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
struct E_{int v,w;};
int n,t,a[1010],len[1010],dis[20010];
basic_string<E_>G[20010];
auto id=[](int i,int k){return k*n+i;};
int main(){
   cin>>n,t=n*16+1;
   for(int i=1;i<=n;i++){
      char s[20];scanf("%s",s);int k=0;
      for(;s[k];k++)a[i]|=s[k]-'0'<<k;
      len[i]=k;
   }
   for(int i=1;i<=n;i++)for(int v=a[i],k=len[i];k>0;v>>=1,k--)for(int j=1;j<=n;j++)if(i!=j)
   if(k<len[j])v==(a[j]&(1<<k)-1)&&(G[id(i,k)]+={id(j,len[j]-k),len[j]-k},0);
   else if(k>len[j])a[j]==(v&(1<<len[j])-1)&&(G[id(i,k)]+={id(i,k-len[j]),0},0);
   else v==a[j]&&(G[id(i,k)]+={t,0},0);
   priority_queue<pair<int,int>>q;
   memset(dis,0x3f,sizeof(dis));
   for(int i=1;i<=n;i++)q.emplace(-(dis[id(i,len[i])]=len[i]),id(i,len[i]));
   for(int u,w;!q.empty();){
      tie(w,u)=q.top(),q.pop();
      if(-w!=dis[u])continue;
      for(auto e:G[u])if(dis[e.v]>dis[u]+e.w){
         dis[e.v]=dis[u]+e.w,q.emplace(-dis[e.v],e.v);
      }
   }cout<<(dis[t]>1e9?0:dis[t]);
   return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4632kb

input:

3
0
01
10

output:

3

result:

ok answer is '3'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4360kb

input:

3
00
01
1

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 1ms
memory: 4364kb

input:

3
00
10
1

output:

0

result:

ok answer is '0'

Test #4:

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

input:

10
1001
1011
01000
00011
01011
1010
00100
10011
11110
0110

output:

13

result:

ok answer is '13'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4312kb

input:

3
1101
1
10

output:

4

result:

ok answer is '4'

Test #6:

score: 0
Accepted
time: 1ms
memory: 4460kb

input:

100
1010011110001
00000100010101
011010100100001
11100001100011
10010001010
1110001110110011
01001100111
1010100110010100
00000100111010
100111001100101
0010000000010
0111110011100110
0100111000001
1100101111110001
1100100110001
10100011010
10100000011000
1111001111001110
000000000101011
10101111011...

output:

102

result:

ok answer is '102'

Test #7:

score: 0
Accepted
time: 1ms
memory: 4368kb

input:

10
0110
001100
0100
0001
100
001010
0010
100010
1100
11101

output:

10

result:

ok answer is '10'

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 4308kb

input:

10
1001
10111
11011
00010
001
001100
110
01110
111101
11100

output:

11

result:

wrong answer expected '10', found '11'