QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#553729 | #1193. Ambiguous Encoding | ccccccyd | WA | 1ms | 5996kb | C++14 | 1.4kb | 2024-09-08 19:05:40 | 2024-09-08 19:05:41 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define mk make_pair
#define ph push_back
#define rep(i,l,r) for(int i(l),i##end(r);i<=i##end;++i)
#define per(i,r,l) for(int i(r),i##end(l);i>=i##end;--i)
using namespace std;
const int N=1e3+20; const ll inf=1e18;
int n,m,len[N]; char s[N][N];
inline bool chk(int x,int d,int y,int len){
rep(i,1,len) if(s[x][d+i]!=s[y][i]) return 0;
return 1;
}
queue<pair<int,int>> q; bool in[N][N]; ll f[N][N],ans=inf;
inline void ins(int i,int j,int x){
if(x<f[i][j]){
f[i][j]=x;
if(!in[i][j]) in[i][j]=1,q.push(mk(i,j));
}
}
signed main(){
// freopen("bad.in", "r", stdin);
// freopen("bad.out", "w", stdout);
scanf("%d",&n),m=16;
rep(i,1,n) scanf("%s",s[i]+1),len[i]=strlen(s[i]+1);
rep(i,1,n) rep(j,0,m) f[i][j]=inf;
rep(i,1,n) ins(i,0,0);
while(!q.empty()){
int x=q.front().first,d=q.front().second; q.pop();
// printf("%d %d %lld\n",x,d,f[x][d]);
in[x][d]=0;
rep(y,1,n) if((d||x!=y)&&chk(x,d,y,min(len[x]-d,len[y]))) {
// printf("%d %d %d %d %lld\n",x,d,y,min(len[x]-d,len[y]),f[x][d]+min(len[x]-d,len[y]));
if(len[x]-d==len[y]){
ans=min(ans,f[x][d]+min(len[x]-d,len[y]));
}else{
if(len[x]-d>len[y]){
ins(x,d+len[y],f[x][d]+min(len[x]-d,len[y]));
}else{
ins(y,len[x]-d,f[x][d]+min(len[x]-d,len[y]));
}
}
}
}
if(ans==inf) puts("-1");
else cout<<ans;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5996kb
input:
3 0 01 10
output:
3
result:
ok answer is '3'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 5772kb
input:
3 00 01 1
output:
-1
result:
wrong answer expected '0', found '-1'