| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 676660 | QwertyPi | Type Printer (IOI08_printer) | C++14 | 0 ms | 0 KiB |
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 SIGMA = 26;
struct node{
node* nxt[SIGMA];
bool word = false;
int heavy = -1;
node() {
fill(nxt, nxt + SIGMA, 0);
}
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';
}