Submission #1176413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176413		ahmedplusplus	Type Printer (IOI08_printer)	C++20	100 / 100	216 ms	119344 KiB

printer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(a)  a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pf push_front
#define pb push_back
#define SZ(x) ((int)(x).size())
#define AhmedPlusPlus ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define YN(X) cout << ( X ? "YES\n" : "NO\n" );
#define hi cerr<<"hi\n";

/*                        ->    NO CLEAN CODE HERE    <-                        */

string ans;
struct Trie {
    struct Node {
        int children[26] = {};
        int f = 0 ,mx = 0, end = 0;
    };

    vector<Node> trie;

    Trie() {
        trie.emplace_back();
    }

    void insert(string& s) {
        int idx = 0;
        for(auto i : s) {
            int nxt = i-'a';

            if(trie[idx].children[nxt] == 0) {
                trie[idx].children[nxt] = trie.size();
                trie.emplace_back();
            }
            idx = trie[idx].children[nxt];
            trie[idx].f++;
        }
        trie[idx].end++;
    }

    void pre(int node = 0){
        int mxx = 0;
        for (int i =0;i<26;i++){
            if (trie[node].children[i]) {
                pre(trie[node].children[i]);
                mxx = max(mxx , trie[trie[node].children[i]].mx);
            }
        }
        trie[node].mx = mxx+1;
    }

    void solve(int node = 0){
        while (trie[node].end--)
            ans+='P';
        int mxx = 0,men=-1;
        for (int i =0;i<26;i++)
            if (trie[node].children[i] != 0 && trie[trie[node].children[i]].mx > mxx)
                mxx = trie[trie[node].children[i]].mx, men = i;
        for (int i =0;i<26;i++){
            if (i == men || trie[node].children[i] == 0)continue;
            ans+=(char)(i+'a');
            solve(trie[node].children[i]);
            ans+=(char)('-');
        }
        if (~men){
            ans+=(char)(men+'a');
            solve(trie[node].children[men]);
            ans+=(char)('-');
        }
    }

};

void pewpew() {

    int n;cin>>n;
    string s;
    Trie tr;
    for (int i =0;i<n;i++){
        cin>>s;
        tr.insert(s);
    }
    tr.pre();
    tr.solve();
    int cnt = 0 , ptr = SZ(ans)-1;
    while(ptr && ans[ptr] == '-')
        cnt++ , ptr--;
    cout << SZ(ans) - cnt << "\n";
    for (int i =0;i<SZ(ans)-cnt ; i++ )cout << ans[i] << "\n";


}

signed main() {
/* ^^^ */    AhmedPlusPlus    /* ^^^ */

//    ->> practice makes perfect

    int Hi = 1;
    //cin >> Hi;
    while (Hi--)
        pewpew();

}

• 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