제출 #1333093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1333093		kakashi342	Type Printer (IOI08_printer)	C++20	20 / 100	76 ms	80428 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]{};
        ll f[26]{};
    };
    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] += (s.size() - i);
            cur = trie[cur].go[ch];
        }
    }
    vector<char> traverse()
    {
        vector<char> ret;
        dfs(ret);
        while (ret.back() == '-')
            ret.pop_back();
        return ret;
    }
    void dfs(vector<char> &ret, int cur = 0)
    {
        bool isLeaf = 1;
        int biggest = -1;
        ll mx = 0;
        for (int ch = 0; ch < 26; ch++)
            if (trie[cur].f[ch] > mx)
                biggest = ch, mx = trie[cur].f[ch];
        for (int ch = 0; ch < 26; ch++)
        {
            if (!trie[cur].go[ch] or ch == biggest)
                continue;
            isLeaf = 0;
            ret.push_back('a' + ch);
            dfs(ret, trie[cur].go[ch]);
            ret.push_back('-');
        }
        if (~biggest)
        {
            isLeaf = 0;
            ret.push_back('a' + biggest);
            dfs(ret, trie[cur].go[biggest]);
            ret.push_back('-');
        }
        if (isLeaf)
            ret.push_back('P');
    }
};
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: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10