QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#183983 | #5119. Perfect Word | zlc | WA | 2ms | 13536kb | C++14 | 1.2kb | 2023-09-20 08:07:59 | 2023-09-20 08:08:00 |
Judging History
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'