Submission #1333110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1333110		kakashi342	Type Printer (IOI08_printer)	C++20	100 / 100	133 ms	109244 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define Kero                                                                                                           \
    ios_base::sync_with_stdio(0);                                                                                      \
    cout.tie(0);                                                                                                       \
    cin.tie(0)
#define ll long long
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define ld long double
#define pii pair<int, int>
#define endl '\n'
#define see(x) " [" << #x << " = " << (x) << "] "
const int INF = 1e9;

// Coding is so easy if you simulate on paper first
struct Trie
{
    struct Node
    {
        int go[26]{};
        int f[26]{};
        bool isEnd= 0;
    };
    vector<Node> trie;
    Trie()
    {
        trie.emplace_back();
    }
    void insert(string &s)
    {
        int cur = 0;
        for (int i = 0; i < s.size(); i++)
        {
            int ch = s[i] - 'a';
            if (!trie[cur].go[ch])
                trie[cur].go[ch] = trie.size(), trie.emplace_back();
            trie[cur].f[ch] = max(trie[cur].f[ch], (int)s.size());
            cur = trie[cur].go[ch];
        }
        trie[cur].isEnd = 1;
    }
    vector<char> traverse()
    {
        vector<char> ret;
        dfs(ret);
        while (ret.back() == '-')
            ret.pop_back();
        return ret;
    }
    void dfs(vector<char> &ret, int cur = 0)
    {
        vector<pii> ordered;
        if(trie[cur].isEnd)
            ret.push_back('P');
        for (int i = 0; i < 26; i++)
            if (trie[cur].f[i] > 0)
                ordered.push_back({trie[cur].f[i], i});
        sort(all(ordered));
        for (auto &[_, ch] : ordered)
            ret.push_back(ch + 'a'), dfs(ret, trie[cur].go[ch]), ret.push_back('-');
    }
};
void solve()
{
    int n;
    cin >> n;
    Trie trie;

    while (n--)
    {
        string s;
        cin >> s;
        trie.insert(s);
    }
    vector<char> ans = trie.traverse();
    cout << ans.size() << endl;
    for (auto &ch : ans)
        cout << ch << endl;
}

signed main()
{
    Kero;
    int 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