제출 #1324529

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324529		shahodz	Type Printer (IOI08_printer)	C++20	100 / 100	203 ms	50540 KiB

printer

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

const int N = 5e5 + 5;

string ans;

struct node {
    bool end = false;
    map<char, int> nxt;

    int &operator[](char c) {
        return nxt[c];
    }
};

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.count(c)) {
                t[u][c] = new_node();
            }
            u = t[u][c];
        }
        t[u].end = true;
    }

    void dfs0(int u) {
        d[u] = 1;
        for (char c = 'a'; c <= 'z'; c++) {
            if (t[u].nxt.count(c)) {
                dfs0(t[u][c]);
                d[u] = max(d[u], d[t[u][c]] + 1);
            }
        }
    }

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

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

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

        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