Submission #59202

#	Time	Username	Problem	Language	Result	Execution time	Memory
59202		TAMREF	Type Printer (IOI08_printer)	C++11	100 / 100	322 ms	51556 KiB

printer

#include <bits/stdc++.h>
using namespace std;

const int mx = 25000 * 20 + 5;
const int root = 0;
const int hi = 25;

struct node{
    bool is_leaf;
    char now;
    int nxt[26];
    int hei;
} trie[mx];

int num_trie = root;

void trie_insert(string& S){
    int now = root;
    for(char &c : S){
        int &nxt = trie[now].nxt[c - 'a'];
        if(!nxt){
            nxt = ++num_trie;
        }
        now = nxt;
        trie[nxt].now = c;
    }
    trie[now].is_leaf = true;
}

void dfs_sort_by_height(int x){
    node &nd = trie[x];
    for(int i = 0, u; i < 26; i++){
        u = nd.nxt[i];
        if(u) dfs_sort_by_height(u);
    }
    stable_sort(nd.nxt, nd.nxt + 26, [](const int &u, const int &v)->bool{
            if(u == 0 || v == 0){
                return u == 0;
            }
            return trie[u].hei < trie[v].hei;
         });
    int highest_child = nd.nxt[hi];

    if(highest_child){
        nd.hei = trie[highest_child].hei + 1;
    }
}

string ans;
void dfs_solve(int x){
    node &nd = trie[x];

    if(nd.is_leaf) ans += 'P';

    for(int i = 0; i < 26; i++){
        int nxt = nd.nxt[i];
        if(nxt){
            ans += trie[nxt].now;
            dfs_solve(nxt);
        }
    }

    if(nd.now) ans += '-';
}

int n;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    string S;
    for(int  i = 0; i < n; i++){
        cin >> S;
        trie_insert(S);
    }
    dfs_sort_by_height(root);
    dfs_solve(root);

    while(!ans.empty() && ans.back() == '-') ans.pop_back();

    cout << ans.size() << '\n';
    for(char &c : ans) cout << c << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10