Submission #1189095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189095		YugiHacker	Type Printer (IOI08_printer)	C++20	100 / 100	99 ms	99072 KiB

printer

/*
	www.youtube.com/YugiHackerChannel
	linktr.ee/YugiHacker
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn
using namespace std;
int n;
string ans;
struct Trie {
    struct Node {
        Node * child[26];
        int cntEnd, depth;
        Node () {
            cntEnd = depth = 0;
            memset (child, 0, sizeof child);
        }
    };

    Node * root;
    Trie() : root(new Node()){}

    void Add (string &s) {
        Node * p = root;
        for (int i=0; i<s.size(); i++) {
            int k = s[i] - 'a';
            if (!p->child[k]) p->child[k] = new Node();
            p = p->child[k];
            p->depth = max(p->depth, (int) s.size() - i);
        }
        p->cntEnd++;
    }
    void dfs(Node *u, bool not_del) {
        for (int i=0; i<u->cntEnd; i++) ans += 'P';
        int v = -1, ma = 0;
        if (not_del) {
            for (int i=0; i<26; i++) {
                if (u->child[i] && u->child[i]->depth > ma) {
                    v = i;
                    ma = u->child[i]->depth;
                }
            }
        }
        for (int i=0; i<26; i++) {
            if (u->child[i]) {
                if (not_del && v == i) continue;
                ans += (char) (i + 'a');
                dfs(u->child[i], 0);
                ans += '-';
            }
        }
        if (not_del && v != -1) {
            ans += (char) ('a' + v);
            dfs(u->child[v], 1);
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    Trie _trie;
    for (int i=1; i<=n; i++) {
        string s; cin >> s;
        _trie.Add(s);
    }
    _trie.dfs(_trie.root, 1);
    cout << ans.size(); el;
    for (char c:ans) cout << c, el;
}

• 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