oj.uz

Submission #648460

# Submission time Handle Problem Language Result Execution time Memory
648460 2022-10-06T15:31:25 Z Elias_Obeid Type Printer (IOI08_printer) C++17
100 / 100
 149 ms 77432 KB 
#include <bits/stdc++.h>
using namespace std;

const int LEN = 25'000;
const int ALPHABET = 26;

struct TrieNode
{
    bool is_leaf;
    int longest_word, longest_letter;
    array<int, ALPHABET> next_nodes;
    TrieNode()
    {
        is_leaf = false;
        longest_word = -1;
        longest_letter = -1;
        next_nodes.fill(-1);
    }
};

int current_trie_node = 0;
array<TrieNode, LEN * ALPHABET> trie;

int fetchNode()
{
    trie[current_trie_node] = TrieNode();
    return current_trie_node++;
}

const int ROOT = fetchNode();

void addWord(const string &word)
{
    int current_node = 0;
    for (int i = 0; i < (int)word.size(); ++i)
    {
        int letter = (word[i] - 'a');
        if (trie[current_node].next_nodes[letter] == -1)
        {
            trie[current_node].next_nodes[letter] = fetchNode();
        }

        if (trie[current_node].longest_word < (int)word.size() - 1 - i)
        {
            trie[current_node].longest_word = (int)word.size() - 1 - i;
            trie[current_node].longest_letter = letter;
        }
        current_node = trie[current_node].next_nodes[letter];
    }
    trie[current_node].is_leaf = true;
}

vector<char> answer;

void depthFirstSearch(int node)
{
    if (trie[node].is_leaf)
    {
        answer.emplace_back('P');
    }

    for (int letter = 0; letter < ALPHABET; ++letter)
    {
        if (trie[node].next_nodes[letter] != -1 && letter != trie[node].longest_letter)
        {
            answer.emplace_back(char(letter + 'a'));
            depthFirstSearch(trie[node].next_nodes[letter]);
        }
    }

    if (trie[node].longest_letter != -1)
    {
        answer.emplace_back(char(trie[node].longest_letter + 'a'));
        depthFirstSearch(trie[node].next_nodes[trie[node].longest_letter]);
    }
    answer.emplace_back('-');
}

int main()
{
    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        string S;
        cin >> S;
        addWord(S);
    }
    depthFirstSearch(ROOT);

    while (!answer.empty() && answer.back() == '-')
    {
        answer.pop_back();
    }

    cout << (int)answer.size() << "\n";
    for (char letter : answer)
    {
        cout << letter << "\n";
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 74032 KB Output is correct
2 Correct 29 ms 73980 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 73936 KB Output is correct
2 Correct 32 ms 73932 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 74068 KB Output is correct
2 Correct 33 ms 74044 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 74016 KB Output is correct
2 Correct 29 ms 74020 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 74068 KB Output is correct
2 Correct 33 ms 74032 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 74068 KB Output is correct
2 Correct 35 ms 74216 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 74184 KB Output is correct
2 Correct 47 ms 74448 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 74596 KB Output is correct
2 Correct 40 ms 74340 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 75196 KB Output is correct
2 Correct 125 ms 76768 KB Output is correct
3 Correct 91 ms 75800 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 74940 KB Output is correct
2 Correct 149 ms 77432 KB Output is correct
3 Correct 96 ms 75972 KB Output is correct
4 Correct 138 ms 77220 KB Output is correct