Submission #1365459

#TimeUsernameProblemLanguageResultExecution timeMemory
1365459hamza_albrahimType Printer (IOI08_printer)C++20
100 / 100
111 ms105972 KiB
#include <bits/stdc++.h>
using namespace std;
 
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
 
// template<class x>
// using ordered_set = tree<x, null_type,less<x>,  rb_tree_tag,tree_order_statistics_node_update>;
 
// template<class x>
// using ordered_multiset = tree<x, null_type,less_equal<x>,  rb_tree_tag,tree_order_statistics_node_update>;
 
#define int long long
#define mod 1'000'000'007

struct node {
    node *adj[26];
    int cnt_end;
    int max_dep, dep;

    node () {
        for(int i = 0; i < 26; i++){
            adj[i] = 0;
        }
        cnt_end = 0;
        dep = 0;
        max_dep = 0;
    }
};

node *root = new node;

void inser(string s){
    node *cur = root;
    for(auto c : s){
        if(!cur -> adj[c - 'a']){
            cur -> adj[c - 'a'] = new node;
        }
        cur = cur -> adj[c - 'a'];
    }
    cur -> cnt_end++;
}

void dfs(node *cur, int p){
    cur -> dep = p + 1;
    cur -> max_dep = cur -> dep;
    for(int i = 0; i < 26; i++){
        if(cur -> adj[i]){
            dfs(cur -> adj[i], cur -> dep);
            cur -> max_dep = max(cur -> adj[i] -> max_dep, cur -> max_dep);
        }
    }
}
string ans = "";
void dfs2(node *cur){
    while(cur -> cnt_end--){
        ans += 'P';
    }
    int m = -1;
    for(int i = 0; i < 26; i++){
        if(cur -> adj[i]){
            if(m == -1 || cur -> adj[i] -> max_dep > cur -> adj[m] -> max_dep){
                m = i;
            }
        }
    }
    for(int i = 0; i < 26; i++){
        if(cur -> adj[i] && i != m){
            ans += (char)(i + 'a');
            dfs2(cur -> adj[i]);
            ans += '-';
        }
    }
    if(m != -1){
        ans += (char)(m + 'a');
        dfs2(cur -> adj[m]);
        ans += '-';
    }
}


signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    
    int n;
    cin>>n;
    for(int i = 0; i < n; i++){
        string s;
        cin>>s;
        inser(s);
    }
    dfs(root, 0);
    dfs2(root);
    while(ans.back() == '-'){
        ans.pop_back();
    }
    cout<<ans.size()<<'\n';
    for(int i = 0; i < ans.size(); i++){
        cout<<ans[i]<<'\n';
    }


    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...