QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#314096 | #1193. Ambiguous Encoding | yinhee | WA | 1ms | 4200kb | C++14 | 2.1kb | 2024-01-25 12:42:27 | 2024-01-25 12:42:27 |
Judging History
answer
// Problem: P6681 [CCO2019] Bad Codes
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6681
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by yinhee.
#include<bits/stdc++.h>
using namespace std;
namespace my_std{
#define mems(x,y) memset(x,y,sizeof x)
#define Mp make_pair
#define eb emplace_back
#define gc getchar
#define pc putchar
#define fi first
#define se second
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a);i>=(b);i--)
#define go(i,u) for(int i=head[u];i;i=e[i].nxt)
typedef long long ll;
typedef pair<int,int> pii;
template<typename T>inline T read(){
T x=0,f=1;char c=gc();
while(!isdigit(c)){if(c=='-')f=-1;c=gc();}
while(isdigit(c))x=x*10+c-48,c=gc();
return x*f;
}
}
using namespace my_std;
const int N=1e4+7,M=1e6+7,inf=0x3f3f3f3f,mod=0;
#define ID(i,j) ((i-1)*(m+1)+j+1)
int n,m,dis[N];
string s[N];bool vis[N];
priority_queue<pii> q;
int tot,head[N];
struct node{int to,nxt,cw;}e[M];
il void add(int u,int v,int w){e[++tot]={v,head[u],w},head[u]=tot;}
void Yorushika(){
scanf("%d",&n),m=16;
rep(i,1,n)cin>>s[i];
rep(i,1,n){
int l=s[i].size();
rep(j,0,l-1){
rep(k,1,n){
int len=l-j;
if(k==i&&!j)continue;
if(s[k].size()>=len){
if(s[i].substr(j,len)==s[k].substr(0,len)){
int w=s[k].size()-len;
add(ID(i,len),ID(k,w),w);
}
}else{
// printf("%d %d\n",i,j);
int sz=s[k].size();
if(s[i].substr(j,sz)==s[k].substr(0,sz)){
int w=len-sz;
add(ID(i,len),ID(i,w),0);
}
}
}
}
}
mems(dis,0x3f);
rep(i,1,n){
int u=ID(i,s[i].size());
dis[u]=s[i].size(),q.push(Mp(-dis[u],u));
}
while(q.size()){
int u=q.top().se;q.pop();
if(vis[u])continue;
vis[u]=1;
go(i,u){
int v=e[i].to;
if(dis[v]<=dis[u]+e[i].cw)continue;
dis[v]=dis[u]+e[i].cw,q.push(Mp(-dis[v],v));
}
}
int ans=inf;
rep(i,1,n)ans=min(ans,dis[ID(i,0)]);
printf("%d\n",ans<1e9?ans:-1);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4120kb
input:
3 0 01 10
output:
3
result:
ok answer is '3'
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 4200kb
input:
3 00 01 1
output:
-1
result:
wrong answer expected '0', found '-1'