Submission #1244477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244477		newsboy	Type Printer (IOI08_printer)	C++20	100 / 100	189 ms	99040 KiB

printer

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <tuple>
#include <cassert>
#include <array>
#include <list>
#include <random>
#include <initializer_list>
#include <chrono>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;

constexpr i64 N = 1E6 + 10;
i64 trie[N][26], f[N], d[N];
i64 tot;

i64 newNode() {
    i64 x = ++tot;
    for (i64 i = 0; i < 26; i++) {
        trie[x][i] = 0;
    }
    f[x] = d[x] = 0;
    return x;
};

void init() {
    tot = 0;
    newNode();
}

void add(string s) {
    i64 o = 1;
    for (i64 i = 0; i < s.size(); i++) {
        i64& p = trie[o][s[i] - 'a'];
        if (!p) {
            p = newNode();
        }
        o = p;
    }
    f[o] = 1;
}

void solve() {
    init();
    i64 n;
    cin >> n;
    for (i64 i = 0; i < n; i++) {
        string s;
        cin >> s;
        add(s);
    }
    auto work = [&](auto& self, i64 x) -> void {
        for (i64 i = 0; i < 26; i++) {
            if (trie[x][i]) {
                self(self, trie[x][i]);
                d[x] = max(d[x], d[trie[x][i]] + 1);
            }
        }
        };
    work(work, 1);
    vector<char> ans;
    auto dfs = [&](auto& self, i64 x) -> void {
        if (f[x]) {
            ans.push_back('P');
        }
        vector<i64> id(26);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](i64 i, i64 j) {
            return d[trie[x][i]] < d[trie[x][j]];
            });
        for (auto i: id) {
            if (!trie[x][i]) {
                continue;
            }
            ans.push_back('a' + i);
            self(self, trie[x][i]);
            ans.push_back('-');
        }
        };
    dfs(dfs, 1);
    while (ans.back() == '-') {
        ans.pop_back();
    }
    cout << ans.size() << '\n';
    for (auto x : ans) {
        cout << char(x) << '\n';
    }
} 

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

• 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