Submission #1129363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129363		goats_9	Type Printer (IOI08_printer)	C++20	100 / 100	174 ms	65720 KiB

printer

/* Author: goats_9 */

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

using ll = long long;

struct Trie {
    const int K = 26;
    const char A = 'a';
    int cnt;
    vector<vector<int>> trie;
    vector<int> stop, id;
    Trie() {
        cnt = 1;
        id.assign(K, -1);
        trie.push_back(id);
        stop.push_back(0);
    }
    void add(string &s) {
        int node = 0;
        for (char ch : s) {
            if (trie[node][ch - A] == -1) {
                trie[node][ch - A] = cnt++;
                trie.push_back(id);
                stop.push_back(0);
            }
            node = trie[node][ch - A];
        }
        stop[node] = 1;
    }
    int find(string &s) {
        int node = 0;
        for (char ch : s) {
            if (trie[node][ch - A] == -1) return -1;
            node = trie[node][ch - A];
        }
        return node;
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    Trie tr;
    while (n--) {
        string s;
        cin >> s;
        tr.add(s);
    }
    vector<int> depth(tr.trie.size());
    function<void(int)> dfs = [&] (int u) {
        for (auto v : tr.trie[u]) {
            if (v == -1) continue;
            dfs(v);
            depth[u] = max(depth[u], depth[v]);
        }
        depth[u]++;
    };
    string moves = "";
    function<void(int)> dfs1 = [&] (int u) {
        vector<pair<int, int>> v;
        for (int i = 0; i < tr.K; i++) {
            if (tr.trie[u][i] == -1) continue;
            v.push_back({depth[tr.trie[u][i]], i});
        }
        sort(v.begin(), v.end());
        if (tr.stop[u]) moves += "P";
        for (auto &[_, i] : v) {
            moves += char(tr.A + i);
            dfs1(tr.trie[u][i]);
            moves += "-";
        }
    };
    dfs(0);
    dfs1(0);
    while (!moves.empty() && moves.back() == '-') moves.pop_back();
    cout << moves.size() << '\n';
    for (auto ch : moves) cout << ch << '\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