Submission #1281565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281565		abuwka	Type Printer (IOI08_printer)	C++20	100 / 100	106 ms	55988 KiB

printer

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define ff first
#define ss second

using namespace std;
using ll = long long;

const ll mod = 1e9 + 7;
const ll INF = 1e18;
const ll N = 1e4 * 25;
const ll con = 37;

ll dx[4] = {-1, 1, 0, 0};
ll dy[4] = {0, 0, -1, 1};

ll n, tim = 1;
struct tr {
    int nx[26];
    bool ok;
    tr() {
        fill(nx, nx+26, -1);
        ok = false;
    }
};
vector<tr> t;
vector<char> d; 
vector<char> ans;   
int ro = -1;
void dsz(int v) {
    bool has = (v == ro);
    for (int c = 0; c < 26; ++c) {
        int u = t[v].nx[c];
        if (u == -1) continue;
        dsz(u);
        if (d[u]) has = true;
    }
    d[v] = has;
}
void dfs(int v) {
    if (t[v].ok) {
        ans.pb ('P');
    }
    int ch = -1;
    vector<int> f;
    for (int c = 0; c < 26; c++) {
        int u = t[v].nx[c];
        if (u == -1) continue;
        f.pb(c);
        if (d[u]) ch = c;
    }
    for (int c : f) {
        if (c == ch) continue;
        int u = t[v].nx[c];
        ans.pb(char('a' + c));
        dfs(u);
        ans.pb('-');
    }
    if (ch != -1) {
        int u = t[v].nx[ch];
        ans.pb(char('a' + ch));
        dfs(u);
    }
}

void solve(){
    int n;
    cin >> n;
    t.pb(tr()); 
    vector<int> s1(n), s2(n);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int v = 0;
        for (char ch : s) {
            int c = ch - 'a';
            if (t[v].nx[c] == -1) {
                t[v].nx[c] = t.size();
                t.pb(tr());
            }
            v = t[v].nx[c];
        }
        t[v].ok = true;
        s1[i] = v;
        s2[i] = (int)s.size();
    }
    int id = 0;
    for (int i = 1; i < n; i++) {
        if (s2[i] > s2[id]) id = i;
    }
    ro = s1[id];
    int m = t.size();
    d.assign(m, 0);
    ans.clear();
    dsz(0);
    dfs(0);
    cout << ans.size() << '\n';
    for (char c : ans) {
        cout << c << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    ll t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    
    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