QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#668461#5119. Perfect Wordji_114514AC ✓4ms8432kbC++201.1kb2024-10-23 14:31:032024-10-23 14:31:04

Judging History

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

  • [2024-10-23 14:31:04]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:8432kb
  • [2024-10-23 14:31:03]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1e5 + 10;
int ch[N][26], ne[N], tot, n, dep[N];
bool st[N], vis[N];
void insert(string &s)
{
    int p = 0;
    for (auto k : s)
    {
        if (!ch[p][k - 'a'])ch[p][k - 'a'] = ++tot, dep[tot] = dep[p] + 1;
        p = ch[p][k - 'a'];
    }
    st[p] = 1;
}

void solve()
{
    cin >> n;
    while (n--)
    {
        string s; cin >> s;
        insert(s);
    }
    queue<int>q;
    for (int i = 0; i < 26; i++)
    {
        int j = ch[0][i];
        if (st[j])q.push(j), vis[j] = 1;
    }
    int res = 0;
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        res = max(res, dep[u]);
        for (int i = 0; i < 26; i++)
        {
            int v = ch[u][i];
            if (v)
            {
                ne[v] = ch[ne[u]][i];
                if (st[v] && vis[ne[v]])q.push(v), vis[v] = 1;
            }
        }
    }
    cout << res;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    while (t--)solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
a
t
b
ab

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3812kb

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: 0
Accepted
time: 0ms
memory: 6128kb

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:

10

result:

ok 1 number(s): "10"

Test #4:

score: 0
Accepted
time: 0ms
memory: 7200kb

input:

5555
fdaaefdad
eacaeb
eeab
decaaddfdfffeb
ebcdeeceabfcded
aeeabcefdfdcb
abfdeeaac
daddadacebffcccb
abacccea
bcbec
ababfdaa
b
fbcccdbcdceafdefa
bdcd
a
ceaabbbae
e
eebeddcedecacafdc
ccdaebfd
ceeefb
baafbad
fadcaefbae
aad
a
dcdddedbdcdeabd
f
fdbccede
ebfb
efadfddddfed
fafefdfbdec
bcacbbafaaeddec
aebfec...

output:

5

result:

ok 1 number(s): "5"

Test #5:

score: 0
Accepted
time: 3ms
memory: 6624kb

input:

6249
a
a
aedbcbebea
bcebbaabeed
ebacbdbbaccdbbe
cceccaacb
ededaa
acdabaebaedab
bacdadacbec
ebbeaebabcebdd
bcec
adc
eeaaadba
eedabbaea
aadaadaecdcd
cdbdbddbababb
ea
ecccbebceddbae
ebaecdaebadad
ddccd
ebcebdcaecae
bccebebdcccbdbca
bccc
ebccdeeedbeea
aaedaeeaadbbbac
bbcee
caeccdbcbee
acbaabecccca
ea
cd...

output:

5

result:

ok 1 number(s): "5"

Test #6:

score: 0
Accepted
time: 0ms
memory: 7084kb

input:

3846
bcabccbcbcaabbaaaba
acabbbacccbbabbbc
ccabcbbacbc
bc
bbabaabcbcbbacbc
bccbcbbbbbcccbc
cabbcacaabcc
acaccccabbabbbbacaaabbaacb
bb
b
bcaccacbacabaaca
cbbacccbbcabcccbcac
bba
accbccacaaaccaccababba
aabcbabacabbaa
babcbbacaccababbbccbbb
acacaccbaccccbbbbcacbacba
aabaccaab
aacbcbbbbacabb
babaacccabc...

output:

6

result:

ok 1 number(s): "6"

Test #7:

score: 0
Accepted
time: 0ms
memory: 7544kb

input:

4166
dabdcacbdaeccdddbbdbaa
ebbe
aaebccdb
bbb
dbbcedbedcdcabebee
ceeeddaeeaabdc
bccdccecbcdbabbbea
bdbe
caebdbdddaaddeeacaacce
bcadededdebddcebdcee
ebddeeccaeacdab
ddedaccdbeeeacaeadcddcd
ca
ceddcedebcbbbaebdcdebcba
acaaaccaadb
da
edab
eadbaae
be
dabebdecdddbbcaaebcec
ababdbdcedcabbabdccea
eecdbdaad...

output:

5

result:

ok 1 number(s): "5"

Test #8:

score: 0
Accepted
time: 4ms
memory: 8432kb

input:

2777
cbccdbdbbeabbadfecfafebfaecdfefabccc
cd
b
eacefbcceada
ffebadacadfddeccadcabefcaeebaad
ebeccfdbfcadefcafefffbbddbedecab
dfbaaddcdafabbaafceadffefeddaaa
cdfdccedccddaceafccbfcaeebeda
cccbdebabcdaeebecbbbaaaebcbcfefbcda
cfefcabeaffcabdaabcbcfebfaeafeef
cdedd
debedaafaafbecfeedccaafeffbdbefedaa
fc...

output:

4

result:

ok 1 number(s): "4"

Test #9:

score: 0
Accepted
time: 3ms
memory: 7008kb

input:

3999
cbcbabccccbbcaaa
cbabaaaa
bbabbcbbbcbabcaaabc
aac
acaacbabcbabbbacabaccbaa
acbcbabcb
abbcbbbbcbaaacc
aabcaccbbbacbababcbaab
cbca
cca
bcabbccabbacaaacbaaaaaa
cabaaaabaabaaababbcc
ccacaaabacabacababcabbcab
babbbac
bbbbcaccbcaab
aca
bcbccccbaaccba
abcacaccccbbcbaccbacac
cacbaabaaabbca
bbcbbacb
cbb...

output:

6

result:

ok 1 number(s): "6"

Test #10:

score: 0
Accepted
time: 0ms
memory: 8428kb

input:

2083
edd
cdaacaeecadeadadd
cbbdccbbdbdddcbbbdb
ac
eeaeaaedbacdbeacbcbabbd
bebbcebbbddddcdddabebaed
daacaccebadbddbaedebdcaecbdee
ebeebeaecceebebdeeec
bbaedcaeadaebacadebacadbebabbaddcdceb
deeaaaecceaccebecccaececcdcdbbcbccdade
dbc
ebeabdeebbdbdcebdecbbdeccbabdcceacecbbc
bbbcadebadaaeeecbaacabedcbeae...

output:

4

result:

ok 1 number(s): "4"

Test #11:

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

input:

33333
knr
kmc
b
d
bmg
rej
fbn
ill
kdc
old
kpf
km
d
gjo
fod
ln
h
pdj
c
qfg
rci
o
eg
rp
n
eg
fig
ihn
h
om
nfg
cd
jhb
e
h
o
rpj
gd
h
lf
f
jb
h
qi
rq
n
km
o
ol
lpk
kp
gek
d
ebh
ch
ei
qm
hjh
eke
kb
djg
e
kl
ckk
m
k
fdr
ejr
m
q
md
bn
r
kf
gkn
nl
op
h
rcb
p
grr
cf
fq
dge
p
ioi
dk
f
pc
kdh
oqe
id
bfk
h
cpc
...

output:

3

result:

ok 1 number(s): "3"

Test #12:

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

input:

49999
cc
a
cb
a
d
c
cc
cc
bb
c
cc
d
dc
bd
cd
bb
bd
c
a
dc
d
cd
b
ab
dc
bb
cc
aa
c
c
ac
d
cb
d
c
a
b
b
ca
da
aa
d
bd
dc
c
b
bd
cc
a
a
cb
a
ad
d
a
bc
dc
a
bb
aa
b
bc
d
bb
c
cb
c
aa
ca
bd
da
ca
a
aa
b
ac
b
da
bd
cc
bb
a
aa
d
bc
ad
d
ca
a
c
b
ad
c
b
bd
c
b
a
d
ad
d
ac
c
cb
a
c
cc
bc
da
b
cd
cb
b
db
c
bb...

output:

2

result:

ok 1 number(s): "2"

Test #13:

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

input:

49999
hd
a
i
i
ig
gi
f
a
f
gh
ic
c
df
eg
cf
e
ei
e
ch
aa
c
dd
c
fh
fg
f
bh
eb
a
hf
e
fd
a
dg
ce
ed
i
h
c
h
g
b
g
e
gg
a
a
ee
a
hg
dh
db
gc
ci
ih
f
fc
ab
ce
f
e
b
i
c
fc
i
c
e
gh
f
de
h
e
cg
b
eb
b
ai
ei
fa
ci
i
e
ic
ab
c
de
gb
fi
dg
hh
ic
c
dc
hf
d
id
i
h
ab
c
h
bb
ca
e
g
g
gh
gh
i
ic
ie
f
b
bb
cd
c...

output:

2

result:

ok 1 number(s): "2"

Test #14:

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

input:

33333
eb
e
dg
b
d
b
bfa
fd
ga
g
ff
c
aeb
dd
ge
ace
cdc
f
gef
a
bdc
a
fbg
da
af
g
f
a
ab
bdd
cb
f
d
cdg
cc
e
eba
a
ef
af
fg
afb
da
fc
dfd
gcf
gd
e
c
b
b
gd
gcb
c
e
d
fe
bgc
f
gcc
bfe
ce
fc
d
deb
da
ffb
age
d
ebf
d
be
b
f
f
fda
d
cdd
d
da
bdb
acg
dcf
b
d
e
cea
e
ee
g
dab
fcd
ac
b
ac
gcg
f
e
ec
g
af
b
...

output:

3

result:

ok 1 number(s): "3"

Test #15:

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

input:

49999
ea
g
ig
ag
i
de
a
de
eg
e
e
db
g
h
a
dg
h
b
c
e
eh
c
e
i
gg
f
fd
g
fa
ed
ha
c
g
e
i
g
bd
c
f
gi
b
g
ca
fa
h
d
b
a
c
ed
i
b
g
h
i
i
ib
g
ie
e
bf
b
hg
a
ih
ei
cc
a
hi
g
f
dg
bd
c
ie
e
h
i
e
h
he
bb
ee
g
e
db
i
ii
i
f
eh
eg
i
h
dc
h
e
a
ga
c
h
d
d
hf
af
ef
a
h
f
d
hb
b
af
d
d
ic
e
a
cb
f
hi
id
g
...

output:

2

result:

ok 1 number(s): "2"