Submission #1324525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1324525		shahodz	Type Printer (IOI08_printer)	C++20	100 / 100	121 ms	57856 KiB

printer

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

const int N = 5e5 + 5;

string ans;

struct node {
    int nxt[26];
    bool end = false;

    node() {
        memset(nxt, 0, sizeof(nxt));
    }
};

struct trie {
    int d[N];
    vector<node> t;

    int new_node() {
        t.push_back(node());
        return t.size() - 1;
    }

    trie() {
        t.clear();
        new_node();
    }

    void insert(string &s) {
        int u = 0;
        for (auto &c: s) {
            if (!t[u].nxt[c - 'a']) {
                t[u].nxt[c - 'a'] = new_node();
            }
            u = t[u].nxt[c - 'a'];
        }
        t[u].end = true;
    }

    void dfs0(int u) {
        d[u] = 1;
        for (int c = 0; c < 26; c++) {
            int v = t[u].nxt[c];
            if (v) {
                dfs0(v);
                d[u] = max(d[u], d[v] + 1);
            }
        }
    }

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

        for (int c = 0; c < 26; c++) {
            int v = t[u].nxt[c];
            if (v && d[v] + 1 < d[u]) {
                ans += char('a' + c);
                dfs(v);
            }
        }

        for (int c = 0; c < 26; c++) {
            int v = t[u].nxt[c];
            if (v && d[v] + 1 == d[u]) {
                ans += char('a' + c);
                dfs(v);
            }
        }

        ans += '-';
    }
};

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

    trie t;

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

    t.dfs0(0);

    t.dfs(0);

    while (ans.back() == '-') {
        ans.pop_back();
    }

    cout << ans.size() << '\n';
    for (auto &c: ans) {
        cout << c << '\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