Submission #871809

#	Time	Username	Problem	Language	Result	Execution time	Memory
871809		rastervc	Type Printer (IOI08_printer)	C++17	100 / 100	163 ms	100552 KiB

printer

#include <iostream>
#include <algorithm>
#include <sstream>
#include <vector>
#include <numeric>

using namespace std;

struct Trie {
    Trie *next[26]{};
    int max_depth = 0;
    bool is_word = false;

    void insert(const char *str) {
        const int ch = *str - 'a';
        if (!next[ch]) next[ch] = new Trie;
        if (*(str + 1)) {
            next[ch]->insert(str + 1);
            max_depth = max(max_depth, 1 + next[ch]->max_depth);
        } else next[ch]->is_word = true, max_depth = max(max_depth, 1);
    }
};

void euler_tour(Trie *trie, stringstream &stream) {
    vector<int> idx(26);
    iota(idx.begin(), idx.end(), 0);

    sort(idx.begin(), idx.end(), [trie](int i, int j) {
        Trie *a = trie->next[i], *b = trie->next[j];
        if (!a && b) return true;
        if (a && !b) return false;
        if (!a && !b) return false;
        return a->max_depth < b->max_depth;
    });

    for (int i = 0; i < 26; ++i)
        if (trie->next[idx[i]]) {
            stream << (char)('a' + idx[i]);
            if (trie->next[idx[i]]->is_word) stream << 'P';
            euler_tour(trie->next[idx[i]], stream);
            stream << '-';
        }
}

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

    int N;
    string str;
    Trie *trie = new Trie;

    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> str;
        trie->insert(str.c_str());
    }

    stringstream stream;
    euler_tour(trie, stream);

    string ans = stream.str();
    int i = 0;
    for (int j = 0; j < (int)ans.size(); ++j)
        if (ans[j] != '-') i = j;

    cout << i + 1 << '\n';
    for (int j = 0; j <= i; ++j)
        cout << ans[j] << '\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