QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#760076 | #1193. Ambiguous Encoding | yuxuzhehuan | WA | 3ms | 31196kb | C++14 | 1.0kb | 2024-11-18 14:37:03 | 2024-11-18 14:37:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define id(i,j) i*(m+1)+j
#define pii pair<int,int>
#define fi first
#define se second
const int _=1e3+3,inf=1e9,__=1e6+1e3+3;
int n,m,l[_],u,di,dis[__],ans=inf;
string c[_];
vector<pii>e[__];
priority_queue<pii,vector<pii>,greater<pii>>q;
signed main()
{ scanf("%d",&n);
for(int i=0;i<n;i++) cin>>c[i],l[i]=c[i].size(),m=max(m,l[i]);
for(int i=0;i<n;i++) for(int j=0;j<l[i];j++) for(int k=0,len=l[i]-j;k<n;k++)
{ if(k==i&&!j) continue;
if(l[k]>=len&&c[i].substr(j,len)==c[k].substr(0,len)) e[id(i,len)].push_back({id(k,l[k]-len),l[k]-len});
if(l[k]<len&&c[i].substr(j,l[k])==c[k].substr(0,l[k])) e[id(i,len)].push_back({id(i,len-l[k]),0});
}
memset(dis,0x3f,sizeof dis);
for(int i=0;i<n;i++) u=id(i,l[i]),q.push({dis[u]=l[i],u});
while(!q.empty())
{ di=q.top().fi,u=q.top().se,q.pop();
if(dis[u]!=di) continue;
for(auto t:e[u]) if(dis[t.fi]>di+t.se) q.push({dis[t.fi]=di+t.se,t.fi});
}
for(int i=0;i<n;i++) ans=min(ans,dis[id(i,0)]);
printf("%d",ans<inf?ans:-1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 31196kb
input:
3 0 01 10
output:
3
result:
ok answer is '3'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 31172kb
input:
3 00 01 1
output:
-1
result:
wrong answer expected '0', found '-1'