oj.uz

Submission #867732

# Submission time Handle Problem Language Result Execution time Memory
867732 2023-10-29T10:32:41 Z fve5 Type Printer (IOI08_printer) C++17
100 / 100
 139 ms 100552 KB 
#include <bits/stdc++.h>
using namespace std;

class Trie {
    struct Node {
        bool is_word;
        int depth;
        Node *children[26];

        Node() : is_word(false), depth(0) {
            fill(children, children + 26, (Node*)NULL);
        }
    } *root;
    vector<char> op;

    void insert(const char *word, int word_size, Node *node) {
        node->depth = max(node->depth, word_size);
        if (*word == '\0') return void(node->is_word = true);
        if (node->children[*word - 'a'] == NULL) {
            node->children[*word - 'a'] = new Node;
        }
        insert(word + 1, word_size, node->children[*word - 'a']);
    }

    void dfs(Node *node) {
        if (node->is_word) op.push_back('P');
        vector<char> ch;
        for (char x = 'a'; x <= 'z'; x++) {
            if (node->children[x - 'a'] != NULL) {
                ch.push_back(x);
            }
        }
        sort(ch.begin(), ch.end(), [&](char a, char b) {
            return node->children[a - 'a']->depth < node->children[b - 'a']->depth;
        });

        for (auto x: ch) {
            op.push_back(x);
            dfs(node->children[x - 'a']);
            op.push_back('-');
        }
    }

public:

    void insert(const char *word, int word_size) { insert(word, word_size, root); }
    vector<char> ops() {
        dfs(root);
        while (!op.empty() && op.back() != 'P') op.pop_back();
        return op;
    }

    Trie() { root = new Node; }
};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int N; cin >> N;

    Trie trie;
    for (int i = 0; i < N; i++) {
        string S; cin >> S;
        trie.insert(S.c_str(), S.size());
    }

    vector<char> ans = trie.ops();
    cout << ans.size() << '\n';
    for (auto c: ans) cout << c << '\n';
}

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 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 1 ms 1116 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2136 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 8 ms 5976 KB Output is correct
2 Correct 17 ms 12636 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 15060 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 52 ms 36916 KB Output is correct
2 Correct 112 ms 84504 KB Output is correct
3 Correct 60 ms 43724 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 29040 KB Output is correct
2 Correct 139 ms 100552 KB Output is correct
3 Correct 67 ms 49616 KB Output is correct
4 Correct 123 ms 94924 KB Output is correct