oj.uz

Submission #536668

# Submission time Handle Problem Language Result Execution time Memory
536668 2022-03-13T18:12:38 Z timreizin Type Printer (IOI08_printer) C++17
100 / 100
 185 ms 57552 KB 
#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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1220 KB Output is correct
2 Correct 6 ms 2080 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3884 KB Output is correct
2 Correct 20 ms 7384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 8068 KB Output is correct
2 Correct 8 ms 2208 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 28536 KB Output is correct
2 Correct 165 ms 57552 KB Output is correct
3 Correct 87 ms 28756 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 15532 KB Output is correct
2 Correct 185 ms 57512 KB Output is correct
3 Correct 122 ms 28868 KB Output is correct
4 Correct 173 ms 57524 KB Output is correct