QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#668429 | #5119. Perfect Word | ji_114514 | WA | 2ms | 5664kb | C++20 | 1.1kb | 2024-10-23 14:22:17 | 2024-10-23 14:22:20 |
Judging History
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'