oj.uz

Submission #931839

# Submission time Handle Problem Language Result Execution time Memory
931839 2024-02-22T12:02:34 Z boris_mihov Type Printer (IOI08_printer) C++17
100 / 100
 166 ms 56328 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>

typedef long long llong;
const int MAXN = 25000 + 10;
const int ALPHABET = 26;
const int MAXLEN = 20;

std::string sol;
struct Trie
{
    struct Node
    {
        int children[ALPHABET];
        bool endHere;
        bool has;
        int dep;
    };

    int cnt;
    Node trie[MAXN * MAXLEN];

    void push(int node, int pos, const std::string &s)
    {
        trie[node].has = true;
        if (pos == s.size())
        {
            trie[node].endHere = true;
            return;
        }

        if (trie[node].children[s[pos] - 'a'] == 0)
        {
            trie[node].children[s[pos] - 'a'] = ++cnt;
        }

        push(trie[node].children[s[pos] - 'a'], pos + 1, s);
        for (int i = 0 ; i < ALPHABET ; ++i)
        {
            if (trie[trie[node].children[i]].has)
            {
                trie[node].dep = std::max(trie[node].dep, trie[trie[node].children[i]].dep + 1);
            }
        }
    }

    void solve(int node)
    {
        int perm[ALPHABET];
        std::iota(perm, perm + ALPHABET, 0);
        std::sort(perm, perm + ALPHABET, [&](int x, int y)
        {
            return trie[trie[node].children[x]].dep < trie[trie[node].children[y]].dep;
        });

        if (trie[node].endHere)
        {
            sol += 'P';
        }

        for (int idx = 0 ; idx < ALPHABET ; ++idx)
        {
            int i = perm[idx];
            if (!trie[trie[node].children[i]].has)
            {
                continue;
            }

            sol += char('a' + i);
            solve(trie[node].children[i]);
            sol += '-';
        }
    }

    Trie()
    {
        cnt = 1;
    }

    void push(const std::string &s)
    {
        push(1, 0, s);
    }
};

int n;
std::string s[MAXN];
Trie trie;

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        trie.push(s[i]);
    }

    trie.solve(1);
    while (sol.back() == '-') sol.pop_back();
    std::cout << sol.size() << '\n';
    for (const char &c : sol)
    {
        std::cout << c << '\n';
    }
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> s[i];
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 7004 KB Output is correct
2 Correct 21 ms 9304 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 11496 KB Output is correct
2 Correct 14 ms 5208 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 21612 KB Output is correct
2 Correct 152 ms 47368 KB Output is correct
3 Correct 82 ms 25760 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 18164 KB Output is correct
2 Correct 166 ms 56328 KB Output is correct
3 Correct 97 ms 30384 KB Output is correct
4 Correct 164 ms 52160 KB Output is correct