QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#668429#5119. Perfect Wordji_114514WA 2ms5664kbC++201.1kb2024-10-23 14:22:172024-10-23 14:22:20

Judging History

This is the latest submission verdict.

  • [2024-10-23 14:22:20]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 5664kb
  • [2024-10-23 14:22:17]
  • Submitted

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];
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);
    }
    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] && ne[v])q.push(v);
            }
        }
    }
    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: 5664kb

input:

4
a
t
b
ab

output:

2

result:

ok 1 number(s): "2"

Test #2:

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

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: 5492kb

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:

11

result:

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