oj.uz

Submission #847813

# Submission time Handle Problem Language Result Execution time Memory
847813 2023-09-10T13:10:49 Z borisAngelov Type Printer (IOI08_printer) C++17
100 / 100
 201 ms 188888 KB 
#include <bits/stdc++.h>

using namespace std;

const int alphabet_size = 26;

int n;

struct trie_node
{
    trie_node *children[alphabet_size];
    pair<int, int> max_passing_length[alphabet_size];
    bool is_end_of_word;

    trie_node()
    {
        is_end_of_word = false;

        for (int i = 0; i < alphabet_size; ++i)
        {
            children[i] = NULL;
            max_passing_length[i].first = 0;
            max_passing_length[i].second = i;
        }
    }
};

trie_node *root = new trie_node;

void insert_word(trie_node *&curr, const string& s, int pos)
{
    if (curr == NULL)
    {
        curr = new trie_node;
    }

    if (pos == s.size())
    {
        //cout << "set end " << endl;
        curr->is_end_of_word = true;
        return;
    }

    curr->max_passing_length[(s[pos] - 'a')].first = max(curr->max_passing_length[(s[pos] - 'a')].first, int(s.size()));
    //cout << "for " << s << " on " << pos << " ::: " << curr->max_passing_length[(s[pos] - 'a')].first << endl;

    insert_word(curr->children[(s[pos] - 'a')], s, pos + 1);
}

vector<char> operations;
int cnt_oparations = 0;

void dfs(trie_node *&curr)
{
    sort(curr->max_passing_length, curr->max_passing_length + alphabet_size);

    if (curr->is_end_of_word == true)
    {
        ++cnt_oparations;
        operations.push_back('P');
    }

    for (int i = 0; i < alphabet_size; ++i)
    {
        if (curr->max_passing_length[i].first != 0 && curr->children[curr->max_passing_length[i].second] != NULL)
        {
            ++cnt_oparations;
            operations.push_back(char('a' + curr->max_passing_length[i].second));

            dfs(curr->children[curr->max_passing_length[i].second]);

            ++cnt_oparations;
            operations.push_back(char('-'));
        }
    }
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        string s;
        cin >> s;
        insert_word(root, s, 0);
    }

    dfs(root);

    cnt_oparations -= root->max_passing_length[alphabet_size - 1].first;

    cout << cnt_oparations << endl;

    for (int i = 0; i < cnt_oparations; ++i)
    {
        cout << operations[i] << "\n";
    }

    return 0;
}

/*
3
print
the
poem
*/

Compilation message

printer.cpp: In function 'void insert_word(trie_node*&, const string&, int)':
printer.cpp:37:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if (pos == s.size())
      |         ~~~~^~~~~~~~~~~

Subtask #1
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 #2
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 #3
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3164 KB Output is correct
2 Correct 4 ms 3932 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 11100 KB Output is correct
2 Correct 26 ms 23756 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 27860 KB Output is correct
2 Correct 8 ms 5980 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 69040 KB Output is correct
2 Correct 178 ms 158536 KB Output is correct
3 Correct 89 ms 81592 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 53868 KB Output is correct
2 Correct 201 ms 188888 KB Output is correct
3 Correct 100 ms 92616 KB Output is correct
4 Correct 191 ms 178264 KB Output is correct