oj.uz

Submission #924978

# Submission time Handle Problem Language Result Execution time Memory
924978 2024-02-10T09:19:52 Z benjaminkleyn Type Printer (IOI08_printer) C++17
100 / 100
 84 ms 60668 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 55900 KB Output is correct
2 Correct 7 ms 55900 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 55900 KB Output is correct
2 Correct 7 ms 55896 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 56156 KB Output is correct
2 Correct 15 ms 56668 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 56812 KB Output is correct
2 Correct 11 ms 56156 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 57840 KB Output is correct
2 Correct 69 ms 60024 KB Output is correct
3 Correct 41 ms 58052 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 57336 KB Output is correct
2 Correct 84 ms 60668 KB Output is correct
3 Correct 45 ms 58348 KB Output is correct
4 Correct 68 ms 60428 KB Output is correct