QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#314014 | #1193. Ambiguous Encoding | 11d10xy | WA | 1ms | 4632kb | C++14 | 1.0kb | 2024-01-25 11:15:04 | 2024-01-25 11:15:06 |
Judging History
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'