Submission #1036378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036378		stdfloat	Type Printer (IOI08_printer)	C++17	100 / 100	121 ms	78216 KiB

printer

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

const int N = (int)5e5 + 1;

string ans;

vector<bool> vis(N);

vector<int> cnt(N);

vector<vector<int>> E(N, vector<int>(26, -1));

void dfs(int x) {
    while (cnt[x]--) ans += 'P';

    for (int i = 0; i < 26; i++) {
        if (E[x][i] != -1 && !vis[E[x][i]]) {
            ans += 'a' + i;
            dfs(E[x][i]);
        }
    }
    for (int i = 0; i < 26; i++) {
        if (E[x][i] != -1 && vis[E[x][i]]) {
            ans += 'a' + i;
            dfs(E[x][i]);
        }
    }

    if (x) ans += '-';
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n;
    cin >> n;

    vector<string> s(n);
    for (auto &i : s) cin >> i;

    int nm = 1;
    vector<int> d(N), pr(N);
    for (auto i : s) {
        int x = 0;
        for (auto j : i) {
            if (E[x][j - 'a'] == -1) {
                pr[nm] = x;
                d[nm] = d[x] + 1;
                E[x][j - 'a'] = nm++;
            }
        
            x = E[x][j - 'a'];
        }

        cnt[x]++;
    }

    int x = max_element(d.begin(), d.end()) - d.begin();
    while (x) {
        vis[x] = true;
        x = pr[x];
    }

    dfs(0);

    while (ans.back() == '-') ans.pop_back();

    cout << (int)ans.size() << '\n';
    for (auto i : ans) cout << i << '\n';
}

• 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