Submission #1313921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313921		algoproclub	Type Printer (IOI08_printer)	C++20	100 / 100	680 ms	85224 KiB

printer

// UUID: 50300012-e83c-45fe-ac14-a575b91c8782
#include <bits/stdc++.h>
using ll = long long;
using namespace std;

vector<vector<int>> t;
vector<char> csak_ide_ne;
vector<bool> veg;
string ans;
int cnt = 0;

void add(string s, bool spec) {
    int cur = 0;
    for (char c : s) {
        if (!t[cur][c-'a']) {
            cnt++;
            t[cur][c-'a'] = cnt;
        }
        if (spec) csak_ide_ne[cur] = c-'a';
        cur = t[cur][c-'a'];
    }
    veg[cur] = true;
}

void dfs(int cur) {
    cerr << cur << "\n";
    if (veg[cur]) ans += 'P';
    for (int i = 0; i < 26; i++) {
        if (csak_ide_ne[cur] == i || t[cur][i] == 0) continue;
        ans += i+'a';
        dfs(t[cur][i]);
        ans += '-';
    }
    int i = csak_ide_ne[cur];
    if (t[cur][i]) {
        ans += i+'a';
        dfs(t[cur][i]);
        ans += '-';
    }
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n; cin >> n;
    vector<string> s(n);
    csak_ide_ne.assign(n*23, 0);
    t.assign(n*23, vector<int>(26, 0));
    veg.resize(n*23, 0);
    int lg = 0;
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        lg = max((int) s[i].size(), lg);
    }

    string y;
    for (string x : s) {
        if ((int) x.size() == lg) {
            y = x;
        }
        add(x, false);
    }
    
    add(y, true);

    dfs(0);
    while (ans.back() == '-') ans.pop_back();
    cout << ans.size() << "\n";
    for (char 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