Submission #924978

#	Time	Username	Problem	Language	Result	Execution time	Memory
924978		benjaminkleyn	Type Printer (IOI08_printer)	C++17	100 / 100	84 ms	60668 KiB

printer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int children[500001][26];
int depth[500001];
int max_depth[500001];
int max_depth_child[500001];
char max_depth_letter[500001];
bool is_end[500001] = {false};
int m = 1;

void insert(string &a)
{
    int p = 0;
    for (char c : a)
    {
        if (children[p][c-'a'] == -1)
            children[p][c-'a'] = m++;
        p = children[p][c-'a'];
    }
    is_end[p] = true;
}

void process(int p = 0)
{
    max_depth[p] = depth[p];
    max_depth_child[p] = -1;
    max_depth_letter[p] = ' ';
    for (char c = 'a'; c <= 'z'; c++)
    {
        if (children[p][c-'a'] == -1)
            continue;

        depth[children[p][c-'a']] = depth[p] + 1;

        process(children[p][c-'a']);

        if (max_depth[children[p][c-'a']] > max_depth[p])
        {
            max_depth[p] = max_depth[children[p][c-'a']];
            max_depth_child[p] = children[p][c-'a'];
            max_depth_letter[p] = c;
        }
    }
}

string moves;
void solve(int p = 0)
{
    if (is_end[p])
        moves.push_back('P');
    for (char c = 'a'; c <= 'z'; c++)
        if (children[p][c-'a'] != -1 && children[p][c-'a'] != max_depth_child[p])
        {
            moves.push_back(c);
            solve(children[p][c-'a']);
            moves.push_back('-');
        }
    if (max_depth_child[p] != -1)
    {
        moves.push_back(max_depth_letter[p]);
        solve(max_depth_child[p]);
        moves.push_back('-');
    }
}

int N;
string s;

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    for (int i = 0; i <= 500000; i++)
        for (int j = 0; j < 26; j++)
            children[i][j] = -1;

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> s;
        insert(s);
    }
    process();
    solve();
    while (moves.size() && moves.back() == '-')
        moves.pop_back();
    cout << moves.size() << '\n';
    for (char move : moves)
        cout << move << '\n';

    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