제출 #1197565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197565		zyadhany	Type Printer (IOI08_printer)	C++20	100 / 100	96 ms	62064 KiB

printer

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>

#define ll long long
#define ld long double
#define pl pair<ll, ll>
#define vi vector<long long>
#define vii vector<vi>
#define vc vector<char>
#define vcc vector<vc>
#define vp vector<pl>
#define mi map<ll,ll>
#define mc map<char,int>
#define sortx(X) sort(X.begin(),X.end());
#define all(X) X.begin(),X.end()
#define allr(X) X.rbegin(),X.rend()
#define ln '\n'
#define YES {cout << "YES\n"; return;}
#define NO {cout << "NO\n"; return;}
#define MUN {cout << "-1\n"; return;}
using namespace std;


class Trie
{
public:
    struct trie_node
    {
        ll cnt;
        ll mx; 
        int next[26];
        trie_node() {
            cnt = mx = 0;
            memset(next, -1, sizeof(next));
        }
    };
    ll get(string &res) {return (get(0, res));}
    void add(string &s) {add(0, s, 0, 0);}
    Trie() {tree.resize(1, trie_node());}
private:
    vector<trie_node> tree;

    ll get(ll m, string &res) {
        for (int i = 0; i < tree[m].cnt; i++)
        {
            res += "P";
        }
        
        for (int i = 0; i < 26; i++)
        {
            if (tree[m].next[i] != -1 && tree[tree[m].next[i]].mx != tree[m].mx) {
                res += (char) 'a'+i;
                get(tree[m].next[i], res);
                res += '-';
            }
        }
        for (int i = 0; i < 26; i++)
        {
            if (tree[m].next[i] != -1 && tree[tree[m].next[i]].mx == tree[m].mx) {
                res += (char) 'a'+i;
                get(tree[m].next[i], res);
                res += '-';
            }
        }

        return 0;
    }

    void add(ll m, string &s, ll h, ll idx) {
        tree[m].mx = max(tree[m].mx, h);
        if (!s[idx]) {
            tree[m].cnt++;
            return;
        }
        int nxt = s[idx] - 'a';
        if (tree[m].next[nxt] == -1) {
            tree[m].next[nxt] = tree.size();
            tree.push_back(trie_node());
        }
        add(tree[m].next[nxt], s, h+1,idx + 1);
        tree[m].mx = max(tree[m].mx, tree[tree[m].next[nxt]].mx);
    }
};

const int MODE = 1e9+7;

void solve(int tc)  {
    ll n;
    cin >> n;

    Trie tr;
    for (int i = 0; i < n; i++)
    {
        string s; cin >> s;
        tr.add(s);
    }
    
    string res = "";
    tr.get(res);
    while (res.back() == '-')
    {
        res.pop_back();
    }
    cout << res.size() << '\n';
    for (auto c : res) cout << c << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int size = 1;    

    // freopen("dec.in", "r", stdin);
    // freopen("dec.out", "w", stdout);

    // cin >> size;
    for (int i = 1; i <= size; i++)
        solve(i);
}

• 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