Submission #1320230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320230		kawhiet	Type Printer (IOI08_printer)	C++20	100 / 100	96 ms	49764 KiB

printer

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

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

constexpr int N = 5e5 + 5;

int trie[N][26], cnt = 0;
bool is_end[N];

void insert(string s) {
    int node = 0;
    for (auto c : s) {
        int j = c - 'a';
        if (trie[node][j] == 0) {
            trie[node][j] = ++cnt;
        }
        node = trie[node][j];
    }
    is_end[node] = 1;
}

int d[N];

void dfs_dist(int u) {
    for (int i = 0; i < 26; i++) {
        if (trie[u][i]) {
            dfs_dist(trie[u][i]);
            d[u] = max(d[u], d[trie[u][i]] + 1);
        }
    }
}

string k;

void dfs(int u) {
    if (is_end[u]) {
        k.push_back('P');
    }
    vector<array<int, 2>> v;
    for (int i = 0; i < 26; i++) {
        if (trie[u][i] == 0) continue;
        v.push_back({d[trie[u][i]], i});
    }
    ranges::sort(v);
    for (auto [_, i] : v) {
        k.push_back(i + 'a');
        dfs(trie[u][i]);
        k.push_back('-');
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        insert(s);
    }
    dfs_dist(0);
    dfs(0);
    while (k.back() == '-') k.pop_back();
    cout << k.size() << '\n';
    for (auto c : k) {
        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