Submission #536668

#	Time	Username	Problem	Language	Result	Execution time	Memory
536668		timreizin	Type Printer (IOI08_printer)	C++17	100 / 100	185 ms	57552 KiB

printer

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <array>
#include <set>

using namespace std;

using ll = long long;

struct Trie
{
    array<int, 26> empty;
    vector<array<int, 26>> child;
    vector<int> end;
    vector<int> lasts;
    
    Trie()
    {
        empty.fill(-1);
        child.push_back(empty);
        end.push_back(0);
        lasts.push_back(-1);
    }
    
    void add(string &s, int i = 0, int v = 0)
    {
        if (i < s.size())
        {
            if (child[v][s[i] - 'a'] == -1)
            {
                child[v][s[i] - 'a'] = (int)child.size();
                child.push_back(empty);
                end.push_back(0);
                lasts.push_back(-1);
            }
            add(s, i + 1, child[v][s[i] - 'a']);
        }
        else ++end[v];
    }
    
    pair<int, int> calc(int v = 0, string help = "")
    {
        pair<int, int> dp{0, 1e9};
        array<pair<int, int>, 26> odp;
        for (int i = 0; i < 26; ++i)
        {
            if (child[v][i] != -1)
            {
                odp[i] = calc(child[v][i], help + char(i + 'a'));
                dp.first += odp[i].first;
            }
        }
        for (int i = 0; i < 26; ++i)
        {
            if (child[v][i] != -1)
            {
                if (dp.first - odp[i].first + odp[i].second < dp.second)
                {
                    dp.second = dp.first - odp[i].first + odp[i].second;
                    lasts[v] = i;
                }
            }
        }
        if (dp.second == 1e9) dp.second = 0;
        if (v != 0) ++dp.second;
        dp.first += 2 + end[v];
        dp.second += end[v];
        return dp;
    }
    
    void order(string &res, int v = 0, bool last = true)
    {
        res += string(end[v], 'P');
        for (int i = 0; i < 26; ++i)
        {
            if (child[v][i] != -1)
            {
                if (last && i == lasts[v]) continue;
                res += char(i + 'a');
                order(res, child[v][i], false);
            }
        }
        if (last)
        {
            if (lasts[v] != -1)
            {
                res += char(lasts[v] + 'a');
                order(res, child[v][lasts[v]], true);
            }
        }
        else res += '-';
    }
    
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    Trie trie;
    while (n--)
    {
        string s;
        cin >> s;
        trie.add(s);
    }
    cout << trie.calc().second << '\n';
    string res;
    trie.order(res);
    for (char i : res) cout << i << '\n';
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10