| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 839662 | ZeroCool | 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;
#define int long long
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
void solve(int T);
void pre();
const int mxn = 405;
const int mxm = 405;
const int SQRT = 500;
const int LOG = 20;
const int inf = 1e18;
const int mod = 1e9 + 7;
const ld eps = 1e-9;
void pre(){
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(false);
cin.tie(0);
#endif
}
int32_t main(){
pre();
int tt = 1;
//cin>>tt;
for(int i = 1;i<=tt;i++){
#ifndef ONLINE_JUDGE
cout<<"Case "<<i<<": "<<endl;
#endif
solve(i);
}
return 0;
}
struct Node{
bool word;
int chars;
map<char, Node*> child;
Node(){
word = false;
chars = 0;
}
~Node(){
for(auto p : child){
delete p.second;
}
}
};
bool cmp(pair<Node*, char> a, pair<Node*, char> b) {
return (a.first->chars) < (b.first->chars);
}
struct Trie{
Node *root;
int totalW;
int totalO;
int totalF;
string ans;
Trie(){
root= new Node();
totalW = 0;
ans = "";
totalO = 0;
}
~Trie(){
delete root;
}
void insert(string word){
Node *curr = root;
int add = 0;
for(char &ch : word){
if(!curr->child.count(ch)){
curr->child[ch] = new Node();
}
curr = curr->child[ch];
curr->chars = max(curr->chars, word.size() - add);
add++;
}
curr->word = true;
totalW++;
}
void dfs(Node *curr, char ch){
if(ch != ' '){
ans += ch;
totalO++;
}
if(curr->word){
ans += 'P';
totalO++;
totalF++;
}
vector<pair<Node*, char> > nex;
for(auto n : curr->child){
nex.pb({n.second, n.first});
}
sort(nex.begin(), nex.end(), cmp);
for(auto n : nex){
dfs(n.first, n.second);
}
if(ch != ' ' && totalF < totalW){
ans+='-';
totalO++;
}
}
void dfs(){
totalF = 0;
dfs(root, ' ');
cout<<totalO<<endl;
for(char c : ans)cout<<c<<endl;
}
};
void solve(int T){
int n;
cin>>n;
Trie t;
for(int i = 0;i<n;i++){
string s;
cin>>s;
t.insert(s);
}
t.dfs();
}