QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#645519#1193. Ambiguous EncodingxmbWA 1ms5936kbC++141.7kb2024-10-16 18:49:402024-10-16 18:49:40

Judging History

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

  • [2024-10-16 18:49:40]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5936kb
  • [2024-10-16 18:49:40]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,id[1010][55],cnt;
long long dis[60100],ans=0x7fffffff;
string s[1010]; 
int head[60010],tot;
struct node{
	int to,nxt,val;
}edge[50000100];
void add(int u,int v,int w){
	edge[++tot].to=v;
	edge[tot].nxt=head[u];
	edge[tot].val=w;
	head[u]=tot;
}
struct dij{
	int x,val;
	bool operator<(const dij&op) const{
		return op.val<val;
	}
};
set<string> st;
priority_queue<dij> que;
bool vis[60010];
void dijkstra(){
	while(!que.empty()){
		int x=que.top().x;
		que.pop();
		if(vis[x])
			continue;
		vis[x]=1;
		for(int i=head[x];i;i=edge[i].nxt){
			int y=edge[i].to;
			if(dis[y]>dis[x]+edge[i].val){
				dis[y]=dis[x]+edge[i].val;
				que.push({y,dis[y]});
			}
		}
	}
}
signed main(){
	memset(dis,0x3f,sizeof(dis));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		cin>>s[i];
	for(int i=1;i<=n;i++)
		for(int j=0;j<s[i].size();j++)
			id[i][j]=++cnt;
	for(int i=1;i<=n;i++)
		for(int j=0;j<s[i].size();j++)
			for(int k=1;k<=n;k++){
				if(s[k].size()<=j){
					if(s[k]!=s[i].substr(s[i].size()-j,s[k].size()))
						continue;
					add(id[i][j],id[i][j-s[k].size()],s[k].size());
				}
				else{
					if(s[i].substr(s[i].size()-j,j)!=s[k].substr(0,j))
						continue;
					add(id[i][j],id[k][s[k].size()-j],j);
				}
			}
	for(int i=1;i<=n;i++)
		st.insert(s[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<s[i].size();j++){
			string k=s[i].substr(0,s[i].size()-j);
			auto it=st.find(k);
			if(it==st.end())
				continue;
			dis[id[i][j]]=s[i].size()-j; 
			que.push({id[i][j],s[i].size()-j});
		}
	dijkstra();
	for(int i=1;i<=n;i++)
		ans=min(ans,dis[id[i][0]]);
	cout<<(ans>1e9/2?-1:ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5936kb

input:

3
0
01
10

output:

3

result:

ok answer is '3'

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 4120kb

input:

3
00
01
1

output:

-1

result:

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