oj.uz

Submission #871809

# Submission time Handle Problem Language Result Execution time Memory
871809 2023-11-11T15:55:02 Z rastervc Type Printer (IOI08_printer) C++17
100 / 100
 163 ms 100552 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 1116 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1884 KB Output is correct
2 Correct 3 ms 2396 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5980 KB Output is correct
2 Correct 23 ms 12636 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15068 KB Output is correct
2 Correct 7 ms 3420 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 37076 KB Output is correct
2 Correct 158 ms 84960 KB Output is correct
3 Correct 72 ms 43724 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 29004 KB Output is correct
2 Correct 163 ms 100552 KB Output is correct
3 Correct 82 ms 49624 KB Output is correct
4 Correct 151 ms 94924 KB Output is correct