Submission #1175998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175998		anas_ahmad7950	Type Printer (IOI08_printer)	C++20	100 / 100	139 ms	60016 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define imie(x) " [" << #x << " = " << (x) << "] "

struct Node {
    int children[26]{};
    int f = 0;
    bool finish = false;
    int mx_depth = 0;
};

struct Trie {
    vector<Node> trie;

    Trie() {
        trie.emplace_back();
    }

    void add(string& s) {
        int node = 0;

        for (int i = 0; i < (int)s.size(); ++i) {
            if (!trie[node].children[s[i] - 'a']) {
                trie[node].children[s[i] - 'a'] = trie.size();
                trie.emplace_back();
            }

            node = trie[node].children[s[i] - 'a'];
            trie[node].f++;
        }
        trie[node].finish = true;
    }
};

void get_depth(int node, int current, Trie& tr) {
    for (int i = 0; i < 26; ++i) {
        int child = tr.trie[node].children[i];

        if (child) {
            get_depth(child, current + 1, tr);
            tr.trie[node].mx_depth = max(tr.trie[node].mx_depth, tr.trie[child].mx_depth);
        }
    }
    tr.trie[node].mx_depth = max(tr.trie[node].mx_depth, current);
}

vector<char> answer;
void DFS(int node, char character, Trie& tr) {
    // cout << imie(node) << imie(character) << endl;
    if (character != '.') {
        answer.push_back(character);
    }
    if (tr.trie[node].finish) {
        answer.push_back('P');
    }

    vector<pair<int, char>> tmp;
    for (int i = 0; i < 26; ++i) {
        int child = tr.trie[node].children[i];

        if (child) {
            tmp.push_back(make_pair(tr.trie[child].mx_depth, char(i + 'a')));
        }
    }
    sort(tmp.begin(), tmp.end());

    for (int i = 0; i < (int)tmp.size(); ++i) {
        auto [x, y] = tmp[i];
        // cout << imie(x) << imie(y) << endl;

        DFS(tr.trie[node].children[y - 'a'], y, tr);
    }
    answer.push_back('-');
}

signed main() {
    int n;
    cin >> n;
    Trie tr;
    string input;
    for (int i = 0; i < n; ++i) {
        cin >> input;
        tr.add(input);
    }

    for (int i = 0; i < 26; ++i) {
        if (tr.trie[0].children[i]) {
            get_depth(tr.trie[0].children[i], 1, tr);
            // cout << imie(tr.trie[tr.trie[0].children[i]].mx_depth) << endl;
        }
    }

    DFS(0, '.', tr);

    while (!answer.empty() && answer.back() == '-')
        answer.pop_back();
    cout << (int)answer.size() << '\n';
    for (const char& itr : answer)
        cout << itr << '\n';
    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