This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int mxc = 26;
struct trie {
trie *chi[mxc];
int len;
int cnt;
int las;
trie() {
cnt = 0;
len = 0;
las = -1;
for(int i = 0; i < mxc; i++)
chi[i] = NULL;
}
};
void insert(trie *root, string s) {
for(char c : s) {
if(root->chi[c - 'a'] == NULL)
root->chi[c - 'a'] = new trie();
root = root->chi[c - 'a'];
}
root->len = s.size();
root->cnt++;
}
trie *root = new trie();
vector<char> ans;
void maxer(int &MAX, int CMP) { if(MAX < CMP) MAX = CMP; }
void dfs(trie *cur) {
for(int i = 0; i < mxc; i++) {
trie *nxt = cur->chi[i];
if(nxt == NULL) continue;
dfs(nxt);
// maxer(cur->len, nxt->len);
if(cur->len < nxt->len) {
cur->len = nxt->len;
cur->las = i;
}
}
}
void solve(trie *cur) {
while(cur->cnt) {
ans.push_back('P');
cur->cnt--;
}
for(int i = 0; i < mxc; i++) {
if(cur->chi[i] == NULL) continue;
if(i == cur->las) continue;
ans.push_back('a' + i);
solve(cur->chi[i]);
ans.push_back('-');
}
if(cur->las != -1) {
int i = cur->las;
ans.push_back('a' + i);
solve(cur->chi[i]);
ans.push_back('-');
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
for(int i = 0; i < n; i++) {
string s;
cin >> s;
insert(root, s);
}
dfs(root);
solve(root);
while(ans.back() != 'P')
ans.pop_back();
cout << ans.size() << endl;
for(char c : ans)
cout << c << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |