제출 #1177707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177707		_naderr	Type Printer (IOI08_printer)	C++20	100 / 100	622 ms	57964 KiB

printer

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define initial first
#define added second
#define sort_all(v) sort(v.begin(), v.end())
#define sz(v) (int)v.size()

#define ya_sayed_ya_badawy            \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);

auto now = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::microseconds>(now.time_since_epoch());

const int MAX = 1e6 + 50;
const int MOD = 1e9 + 7;
const int OO = 1e9;
const double EPS = (double)1e-9;
const int ALPHA = 26;

int height[MAX];

struct Trie
{

    struct Node
    {
        int child[ALPHA] = {};
        int f = 0;
        bool end = false;
    };

    vector<Node> trie;
    vector<char> operations;

    Trie()
    {
        trie.emplace_back();
    }

    void insert(string &s)
    {

        int node = 0;

        for (auto &ch : s)
        {
            int ch_idx = ch - 'a';

            if (!trie[node].child[ch_idx])
            {
                trie[node].child[ch_idx] = (int)trie.size();
                trie.emplace_back();
            }

            node = trie[node].child[ch_idx];
            trie[node].f++;
        }

        trie[node].end = true;

        return;
    }

    int fill_heights(int node = 0)
    {
        bool leaf = true;
        for (int i = 0; i < ALPHA; i++)
        {
            if (trie[node].child[i])
            {
                leaf = false;
                break;
            }
        }

        if (leaf)
        {
            return height[node] = 0;
        }

        for (int i = 0; i < ALPHA; i++)
        {
            if (trie[node].child[i])
            {
                height[node] = max(height[node], 1 + fill_heights(trie[node].child[i]));
            }
        }

        return height[node];
    }

    void print(int node = 0)
    {

        if (trie[node].end)
        {
            operations.push_back('P');
        }

        int mx = -1;

        for (int i = 0; i < ALPHA; i++)
        {
            if (trie[node].child[i])
            {
                mx = max(mx, height[trie[node].child[i]]);
            }
        }

        for (int i = 0; i < ALPHA; i++)
        {
            if (trie[node].child[i] && mx != height[trie[node].child[i]])
            {
                operations.push_back(('a' + i));

                print(trie[node].child[i]);

                operations.push_back(('-'));
            }
        }

        for (int i = 0; i < ALPHA; i++)
        {
            if (trie[node].child[i] && mx == height[trie[node].child[i]])
            {
                operations.push_back(('a' + i));

                print(trie[node].child[i]);

                operations.push_back(('-'));
            }
        }

        return;
    }
};

void solve()
{
    int n;
    cin >> n;

    Trie tr;

    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        tr.insert(s);
    }

    tr.fill_heights();

    tr.print();

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

    cout << sz(tr.operations) << endl;

    for (int i = 0; i < sz(tr.operations); i++)
    {
        cout << tr.operations[i] << endl;
    }
}

signed main()
{
    ya_sayed_ya_badawy int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        // cout << endl;
    }
    return 0;
}

• 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