Submission #1268234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268234		smtyon	Type Printer (IOI08_printer)	C++20	100 / 100	614 ms	59244 KiB

printer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define SMTYON ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define hi cerr<<"HI\n";
/*                        ->    NO CLEAN CODE HERE    <-                        */

struct Node {
    bool isEnd = false;
    int len = 1;
    int adj[26]{};
    Node() { memset(adj, 0, sizeof adj); }
};

class Trie {
public:
    vector<Node> h;
    Trie() { h.emplace_back(); }

    void insert(const string &s) {
        int node = 0;
        for (char c : s) {
            int id = c - 'a';
            if (!h[node].adj[id]) {
                h[node].adj[id] = h.size();
                h.emplace_back();
            }
            node = h[node].adj[id];
        }
        h[node].isEnd = true;
    }
    void start(int node) {
        int mx = 0;
        for (int c = 0; c < 26; c++) {
            if (h[node].adj[c]) {
                int child = h[node].adj[c];
                start(child);
                mx = max(mx, h[child].len);
            }
        }
        h[node].len = mx+1;
    }
    void dfs(int u, vector<char> &ops) {
        if (h[u].isEnd) ops.push_back('P');

        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        for (int c = 0; c < 26; c++) {
            if (h[u].adj[c]) {
                int child = h[u].adj[c];
                q.push({h[child].len, c});
                // ops.push_back('a' + c);
                // dfs(h[u].adj[c], ops);
                // ops.push_back('-');
            }
        }

        while (!q.empty()) {
            pair<int, int> p = q.top();
            q.pop();
            ops.push_back('a' + p.second);
            dfs(h[u].adj[p.second], ops);
            ops.push_back('-');
        }
    }
};

signed main() {
    /* ^^^ */
    SMTYON /* ^^^ */
    //    ->> practice makes perfect
    int N;
    cin >> N;
    Trie t;
    vector<string> words(N);
    for (int i = 0; i < N; i++) {
        cin >> words[i];
        t.insert(words[i]);
    }

    vector<char> ops;
    t.start(0);
    t.dfs(0, ops);
    int n = ops.size();
    for (int i = n -1; i >= 0; i--) {
        if (ops[i] == '-')ops.pop_back();
        else break;
    }
    cout << ops.size() << endl;
    for (auto x : ops) cout << x << endl;

}

• 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