QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#314096#1193. Ambiguous EncodingyinheeWA 1ms4200kbC++142.1kb2024-01-25 12:42:272024-01-25 12:42:27

Judging History

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

  • [2024-01-25 12:42:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4200kb
  • [2024-01-25 12:42:27]
  • 提交

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();
}

Details

Tip: Click on the bar to expand more detailed information

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'