QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#760126#1193. Ambiguous EncodingyuxuzhehuanWA 3ms31156kbC++141.0kb2024-11-18 14:55:362024-11-18 14:55:44

Judging History

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

  • [2024-11-18 14:55:44]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:31156kb
  • [2024-11-18 14:55:36]
  • 提交

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: 0ms
memory: 31144kb

input:

3
0
01
10

output:

3

result:

ok answer is '3'

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 31156kb

input:

3
00
01
1

output:

-1

result:

wrong answer expected '0', found '-1'