Submission #1313796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313796		miszorimarci	Type Printer (IOI08_printer)	C++20	100 / 100	92 ms	51128 KiB

printer

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

struct node {
    int nxt[26];
    bool end;
    node() {
        memset(nxt, -1, sizeof(nxt));
        end = false;
    }
};

vector<node> t;
vector<char> ans;
vector<int> depth;

int calc_depth(int u) {
    int best = 0;
    for (int c = 0; c < 26; c++) {
        int v = t[u].nxt[c];
        if (v != -1)
            best = max(best, 1 + calc_depth(v));
    }
    return depth[u] = best;
}

void dfs(int u) {
    if (t[u].end)
        ans.push_back('P');

    vector<pair<int,int>> ch;
    for (int c = 0; c < 26; c++) {
        int v = t[u].nxt[c];
        if (v != -1)
            ch.push_back({depth[v], c});
    }

    sort(ch.begin(), ch.end()); 

    for (auto [d, c] : ch) {
        int v = t[u].nxt[c];
        ans.push_back(c+'a');
        dfs(v);
        ans.push_back('-');
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;

    t.reserve(2000000);
    t.push_back(node());

    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        int cur = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[cur].nxt[c] == -1) {
                t[cur].nxt[c] = t.size();
                t.push_back(node());
            }
            cur = t[cur].nxt[c];
        }
        t[cur].end = true;
    }

    depth.assign(t.size(), 0);
    calc_depth(0);
    dfs(0);

    while (!ans.empty() && ans.back() == '-') ans.pop_back();

    cout << ans.size() << "\n";
    for (char c : ans) cout << c << "\n";
}

• 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