/**
* author: wxhtzdy
* created: 09.08.2022 10:49:03
**/
#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 a, string b) {
if (a.size() != b.size()) {
return a.size() < b.size();
} else {
return a < b;
}
});
const int A = 26;
vector<vector<int>> trie(1, vector<int>(A, -1));
vector<int> dp(1, 0);
for (int i = 0; i < n; i++) {
int p = 0;
vector<int> v(1, p);
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>(A, -1));
dp.push_back(0);
}
p = trie[p][c];
v.push_back(p);
}
int sz = (int) v.size();
int mx = max(dp[v[sz - 2]], dp[v[sz - 1]]) + 1;
dp[v[sz - 2]] = max(dp[v[sz - 2]], mx);
dp[v[sz - 1]] = max(dp[v[sz - 1]], mx);
}
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 |
0 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Incorrect |
474 ms |
102816 KB |
Output isn't correct |
| 5 |
Correct |
34 ms |
6600 KB |
Output is correct |
| 6 |
Incorrect |
49 ms |
44756 KB |
Output isn't correct |
| 7 |
Incorrect |
39 ms |
44476 KB |
Output isn't correct |
| 8 |
Incorrect |
37 ms |
44332 KB |
Output isn't correct |
| 9 |
Incorrect |
100 ms |
51344 KB |
Output isn't correct |
| 10 |
Incorrect |
38 ms |
44388 KB |
Output isn't correct |
