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;
vector<char> res;
struct Trie{
struct Node{
Node* child[26];
int cnt, exist;
Node(){
for(int i = 0; i < 26; i++) child[i] = NULL;
exist = cnt = 0;
}
};
int cur;
Node* root;
Trie() : cur(0){
root = new Node();
}
void add_string(string s){
Node* p = root;
for (auto f : s) {
int c = f - 'a';
if (p->child[c] == NULL) p->child[c] = new Node();
p = p->child[c];
p->cnt++;
}
p->exist++;
}
void Trie_Recursive(Node* p){
vector<pair<Node*, int>> tmp;
for(int i = 0; i < 26; i++){
if(p->child[i] != NULL){
tmp.push_back({p->child[i], i});
}
}
sort(tmp.begin(), tmp.end(), [](pair<Node*, int> x, pair<Node*, int> y){
if(x.first->cnt < y.first->cnt) return true;
return false;
});
for(auto it : tmp){
res.push_back(char(it.second + 'a'));
Trie_Recursive(it.first);
res.push_back('-');
}
while(p->exist > 0){
res.push_back('P');
p->exist--;
}
}
};
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
Trie T;
for(int i = 0; i < n; i++){
string s; cin >> s;
T.add_string(s);
}
T.Trie_Recursive(T.root);
int cnt = 0;
vector<char> ans;
for(auto x : res){
if(cnt == n) break;
ans.push_back(x);
if(x == 'P') cnt++;
}
cout << ans.size() << endl;
for(auto x : ans) cout << x << endl;
}
# | 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... |