Submission #1281748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281748		abuwka	Type Printer (IOI08_printer)	C++20	100 / 100	118 ms	56096 KiB

printer

// https://oj.uz/problem/view/IOI08_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};

int n, ro = -1;
struct tr{
    int nx[26];
    bool ok;
    tr(){
        fill(nx, nx + 26, -1);
        ok = false;
    }
};
vector<tr> t;
vector<char> d, ans;

void dsz(int v){
    char is = (v == ro);
    for(int c = 0; c < 26; c++){
        int u = t[v].nx[c];
        if(u == -1) continue;
        dsz(u);
        if(d[u]) is = true;
    }
    d[v] = is; 
}

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 x : f){
        if(x == ch) continue;
        ans.pb(char('a' + x));
        dfs(t[v].nx[x]);
        ans.pb('-');
    }
    if(ch != -1){
        ans.pb(char('a' + ch));
        dfs(t[v].nx[ch]);
    }
}

void solve(){
    cin >> n;
    vector<int> s1(n), s2(n);
    t.pb(tr());
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        int v = 0;
        for(char c : s){
            if(t[v].nx[c - 'a'] == -1) {
                t[v].nx[c - 'a'] = t.size();
                t.pb(tr());
            }
            v = t[v].nx[c - 'a'];
        }
        t[v].ok = true;
        s1[i] = v;
        s2[i] = 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