QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#183983#5119. Perfect WordzlcWA 2ms13536kbC++141.2kb2023-09-20 08:07:592023-09-20 08:08:00

Judging History

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

  • [2023-09-20 08:08:00]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:13536kb
  • [2023-09-20 08:07:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
inline int R()
{
	char c;int sign=1,res=0;
	while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1;res=res+c-'0';
	while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
	return res*sign;
}
const int Maxn=1e5+5;
char s[Maxn];
int sqn,son[Maxn*4][26],tot=1,num[Maxn*4],fa[Maxn*4],ch[Maxn*4];
int top,h[Maxn],hh[Maxn];
void check(int pos)
{
	top=0;
	while(pos!=1)
	{
		h[++top]=pos;
		hh[ top]=ch[pos];
		pos=fa[pos];
	}
	for(int j=top;j>=1;j--)
	{
		int now=1;
		for(int i=j;i>=1;i--)
		{
			now=son[now][hh[i]];
			if(now==0)return;
			if(num[now]==0) return;
		}
	}
	printf("%d\n",top);
	exit(0);
}
void dfs(int pos,int deep)
{
	if(pos>1&&num[pos]==0) return;
	if(deep>sqn+1) return;
	for(int i=0;i<26;i++)
	{
		if(son[pos][i])
		dfs(son[pos][i],deep+1);
	}
	check(pos);
}
signed main()
{
	int n=R(),m=0;
	fa[1]=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		int now=1,len=strlen(s);
		m+=len;
		for(int j=0;j<len;j++)
		{
			if(son[now][s[j]-'a']==0)
			{
				son[now][s[j]-'a']=++tot;
				ch[tot]=s[j]-'a';
				fa[tot]=now;
			}
			now=son[now][s[j]-'a']; 
		}	
		num[now]++;	
	}
	int now=1;	sqn=sqrt(2*m)+1;
	dfs(1,0);
}
// sqn(sqn+1)  = 2n

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 10036kb

input:

4
a
t
b
ab

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 2ms
memory: 10128kb

input:

310
a
aa
aaa
aaaa
aaaaa
aaaaaa
aaaaaaa
aaaaaaaa
aaaaaaaaa
aaaaaaaaaa
aaaaaaaaaaa
aaaaaaaaaaaa
aaaaaaaaaaaaa
aaaaaaaaaaaaaa
aaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaa...

output:

300

result:

ok 1 number(s): "300"

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 13536kb

input:

4347
bbaaaab
aabab
bbaaaaababaaaba
aababaaaabbbabababaaaba
ababbabbbbbabbbabbab
bbbbbbb
bbbabbbabbabaab
aabbbbabbbbaa
aabaaabbbbbabaaababaa
aaabababba
aaababbaabab
abbababbabbab
bababaabbbbaaa
aaaaaabaaaababaa
ababaababba
babaababbbababaaab
bb
abbbaaaababa
b
ab
aaabbbbb
abaabaaaaababbbab
bbaaabaab
b...

output:

8

result:

wrong answer 1st numbers differ - expected: '10', found: '8'