#include <bits/stdc++.h>
using namespace std;
const int SIGMA = 26;
struct node{
node* nxt[SIGMA];
bool word = false;
int heavy = -1;
node() {
fill(nxt, nxt + SIGMA, nullptr);
}
node* extend(int c){
if(!nxt[c]) nxt[c] = new node;
return nxt[c];
}
node* extend_heavy(int c){
heavy = c;
return nxt[c];
}
};
string ans;
void dfs(node *root){
if(root->word) ans.push_back('P');
for(int c = 0; c < SIGMA; c++){
if(root->nxt[c] && root->heavy != c){
ans.push_back('a' + c);
dfs(root->nxt[c]);
ans.push_back('-');
}
}
if(root->heavy != -1){
ans.push_back('a' + root->heavy);
dfs(root->nxt[root->heavy]);
ans.push_back('-');
}
}
node *root = new node;
int main(){
int n; cin >> n;
vector<string> vs;
for(int i = 0; i < n; i++){
string s; cin >> s;
vs.push_back(s);
node *x = root;
for(auto c : s){
x = x->extend(c - 'a');
}
x->word = true;
}
sort(vs.begin(), vs.end(), [](string a, string b){
return a.size() < b.size();
});
{
node *x = root;
for(auto c : vs.back()){
x = x->extend_heavy(c - 'a');
}
}
dfs(root);
while(ans.back() == '-') ans.pop_back();
cout << ans.size() << '\n';
for(auto c : ans) cout << c << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1748 KB |
Output is correct |
2 |
Correct |
3 ms |
2260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
6004 KB |
Output is correct |
2 |
Correct |
21 ms |
12640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
15112 KB |
Output is correct |
2 |
Correct |
15 ms |
3660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
37404 KB |
Output is correct |
2 |
Correct |
143 ms |
84628 KB |
Output is correct |
3 |
Correct |
94 ms |
44488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
29552 KB |
Output is correct |
2 |
Correct |
170 ms |
100660 KB |
Output is correct |
3 |
Correct |
105 ms |
50976 KB |
Output is correct |
4 |
Correct |
147 ms |
95576 KB |
Output is correct |