/**
* author: wxhtzdy
* created: 22.06.2022 11:13:52
**/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
reverse(s[i].begin(), s[i].end());
}
sort(s.begin(), s.end(), [&](string x, string y) {
if (x.size() != y.size()) {
return x.size() < y.size();
} else {
return x < y;
}
});
vector<vector<int>> trie;
vector<int> dp(1, 0);
trie.push_back(vector<int>(26, -1));
for (int i = 0; i < n; i++) {
int p = 0;
int t = 0;
int mx = 0;
for (int j = 0; j < (int) s[i].size(); j++) {
int c = (int) (s[i][j] - 'a');
if (trie[p][c] == -1) {
trie[p][c] = (int) trie.size();
trie.push_back(vector<int>(26, -1));
dp.push_back(0);
}
p = trie[p][c];
if (j >= (int) s[i].size() - 2) {
mx = max(mx, dp[p]);
}
if (j == (int) s[i].size() - 2) {
t = p;
}
}
if (s[i].size() <= 1) {
mx = dp[0];
}
if (t != -1) {
dp[t] = max(dp[t], mx + 1);
}
dp[p] = max(dp[p], mx + 1);
}
cout << *max_element(dp.begin(), dp.end()) << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Incorrect |
414 ms |
100040 KB |
Output isn't correct |
| 5 |
Correct |
33 ms |
3684 KB |
Output is correct |
| 6 |
Incorrect |
50 ms |
43068 KB |
Output isn't correct |
| 7 |
Incorrect |
41 ms |
42888 KB |
Output isn't correct |
| 8 |
Incorrect |
36 ms |
42868 KB |
Output isn't correct |
| 9 |
Incorrect |
89 ms |
47272 KB |
Output isn't correct |
| 10 |
Incorrect |
41 ms |
42832 KB |
Output isn't correct |
