Submission #1274651

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274651		ngunguoi45	Type Printer (IOI08_printer)	C++17	100 / 100	149 ms	105980 KiB

printer

#include <bits/stdc++.h>
#define add emplace_back

using namespace std;

struct Node {
    Node *child[26];
    int ended, dep, vis;
    Node () {
        for (int i = 0;i < 26; i++) child[i] = nullptr;
        ended = 0;
        dep = 0;
        vis = 0;
    }
};

struct Trie {
    Node *root;
    Trie () {
        root = new Node();
    }
    void insert (const string &s) {
        Node *p = root;
        for (auto c: s) {
            if (p->child[c-'a'] == nullptr) p->child[c-'a'] = new Node();
            p = p->child[c-'a'];
        }
        p->ended++;
    }
    void dfs (Node *p) {
        p->dep = 1;
        for (int i = 0;i < 26; i++) if (p->child[i] != nullptr) {
            dfs (p->child[i]);
            p->dep = max (p->dep, p->child[i]->dep + 1);
        }
    }
    void type_and_print() {
        int prv_del = 0;
        vector<char> ans;
        stack<Node*> st;
        Node *s = root;
        st.push(s);

        while ((int)st.size()) {
            Node *p = st.top();
            p->vis = 1;
            if (p->ended) {
                for (int i = 0;i < p->ended; i++) ans.add('P');
                p->ended = 0;
            }
            int mx = -1, charmax = -1;
            for (int i = 0;i < 26; i++) if (p->child[i] != nullptr) {
                if (p->child[i]->vis == 0 && p->child[i]->dep > mx) {
                    mx = p->child[i]->dep;
                    charmax = i;
                }
            }
            bool found = 0;
            for (int i = 0;i < 26; i++) if (p->child[i] != nullptr) {
                if (i == charmax) continue;
                if (p->child[i]->vis == 0) {
                    st.push(p->child[i]);
                    ans.add((char)(i+'a'));
                    prv_del = 0;
                    found = 1;
                    break;
                }
            }
            if (!found && mx > -1) {
                prv_del = 0;
                st.push(p->child[charmax]);
                ans.add((char)(charmax+'a'));
            }
            else if (!found) {
                st.pop();
                ans.add('-');
                prv_del++;
            }
        }
        cout << (int)ans.size() - prv_del << "\n";
        for (int i = 0;i < (int)ans.size() - prv_del; i++) cout << ans[i] << '\n';
    }
};

int n;
string s;
Trie Wiki;

int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0;i < n; i++) {
        cin >> s;
        Wiki.insert(s);
    }
    Wiki.dfs(Wiki.root);
    Wiki.type_and_print();
    return 0;
}

• 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