oj.uz

Submission #554897

# Submission time Handle Problem Language Result Execution time Memory
554897 2022-04-29T14:38:47 Z alextodoran Type Printer (IOI08_printer) C++17
100 / 100
 122 ms 99652 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector <char> sol;

struct Trie {
    int depth; int cnt = 0;
    Trie* sons[26];
    Trie () {
        cnt = 0;
        depth = 0;
        for (int i = 0; i < 26; i++) {
            sons[i] = NULL;
        }
    }
    void add (char* str) {
        if (*str == '\0') {
            cnt++;
            return;
        }
        int i = (int) (*str - 'a');
        if (sons[i] == NULL) {
            sons[i] = new Trie();
        }
        sons[i]->add(str + 1);
        depth = max(depth, sons[i]->depth + 1);
    }
    void dfs (bool ret = false) {
        while (cnt--) {
            sol.push_back('P');
        }
        int last = -1;
        for (int i = 0; i < 26; i++) {
            if (sons[i] != NULL) {
                if (last == -1 || sons[i]->depth > sons[last]->depth) {
                    last = i;
                }
            }
        }
        if (last != -1) {
            for (int i = 0; i < 26; i++) {
                if (sons[i] != NULL && i != last) {
                    sol.push_back((char) ('a' + i));
                    sons[i]->dfs(true);
                }
            }
            sol.push_back((char) ('a' + last));
            sons[last]->dfs(ret);
        }
        if (ret == true) {
            sol.push_back('-');
        }
    }
};

Trie root;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        char str[21];
        cin >> str;
        root.add(str);
    }
    root.dfs(false);

    cout << (int) sol.size() << "\n";
    for (char x : sol) {
        cout << x << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 320 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 212 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 452 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1748 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct

Subtask #7
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 36604 KB Output is correct
2 Correct 105 ms 83768 KB Output is correct
3 Correct 58 ms 43204 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 28612 KB Output is correct
2 Correct 122 ms 99652 KB Output is correct
3 Correct 66 ms 48988 KB Output is correct
4 Correct 114 ms 94020 KB Output is correct