#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x.size())
using namespace std;
const int N = 500000;
int edges[N][27];
vector<int> depth(N, -1);
int counter;
void dfs(int x) {
if (edges[x][26]) {
cout << "P\n";
--counter;
}
for (int i = 0; i <= 20; ++i) {
for (int j = 0; j < 26; ++j) {
if (edges[x][j] != 0 && depth[edges[x][j]] == i) {
cout << (char)('a'+j) << "\n";
dfs(edges[x][j]);
}
}
}
if (counter > 0) cout << "-\n";
}
void solve() {
int n, vs = 1, c;
cin >> n;
string s;
for (int i = 0; i < n; ++i) {
cin >> s;
c = 0;
for (int j = 0; j < sz(s); ++j) {
if (edges[c][s[j]-'a'] == 0) {
edges[c][s[j]-'a'] = vs;
++vs;
}
c = edges[c][s[j]-'a'];
}
depth[c] = 0;
edges[c][26] = 1;
}
for (int i = vs-1; i >= 0; --i) {
for (int j = 0; j < 26; ++j) {
if (edges[i][j] != 0) {
depth[i] = max(depth[i], depth[edges[i][j]]+1);
}
}
}
int ans = ((vs-1)*2)+n-depth[0];
cout << ans << "\n";
counter = n;
dfs(0);
return;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2260 KB |
Output is correct |
2 |
Correct |
1 ms |
2260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2304 KB |
Output is correct |
2 |
Correct |
1 ms |
2260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2260 KB |
Output is correct |
2 |
Correct |
1 ms |
2260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2260 KB |
Output is correct |
2 |
Correct |
2 ms |
2260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2260 KB |
Output is correct |
2 |
Correct |
4 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2948 KB |
Output is correct |
2 |
Correct |
6 ms |
3204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
4948 KB |
Output is correct |
2 |
Correct |
31 ms |
8296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
9332 KB |
Output is correct |
2 |
Correct |
9 ms |
3796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
80 ms |
20008 KB |
Output is correct |
2 |
Correct |
180 ms |
42892 KB |
Output is correct |
3 |
Correct |
94 ms |
23080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
16088 KB |
Output is correct |
2 |
Correct |
227 ms |
50600 KB |
Output is correct |
3 |
Correct |
105 ms |
25892 KB |
Output is correct |
4 |
Correct |
195 ms |
47820 KB |
Output is correct |