제출 #1171124

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171124		mousebeaver	Type Printer (IOI08_printer)	C++20	10 / 100	55 ms	41956 KiB

printer

#define ll long long
#define subINF numeric_limits<ll>::min()/2
#define pll pair<ll, ll>
#define ppl pair<pll, ll>
#define BITS 32
#include <bits/stdc++.h>
using namespace std;

void dfs(vector<bool>& mark, vector<vector<ll>>& trie, vector<char>& output, ll node, vector<ll>& h)
{
    if(mark[node])
        output.push_back('P');

    vector<pll> child(0);

    for(ll i = 0; i < 26; i++)
    {
        if(trie[node][i] != -1)
        {
            child.push_back({h[trie[node][i]], i});
        }
    }
    
    sort(child.begin(), child.end());

    for(pll p : child)
    {
        ll i = p.second;
        output.push_back((char) (((int) 'a') + i));
        dfs(mark, trie, output, trie[node][i], h);
    }

    output.push_back('-');
}

void preDFS(vector<vector<ll>>& trie, ll node, vector<ll>& h)
{
    h[node] = 0;

    for(ll i = 0; i < 26; i++)
    {
        if(trie[node][i] != -1)
        {
            preDFS(trie, trie[node][i], h);
            h[node] = max(h[node], h[trie[node][i]]);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n;
    cin>>n;
    vector<vector<ll>> trie(1, vector<ll> (26, -1));
    vector<bool> mark(1, false);


    for(ll i = 0; i < n; i++)
    {
        string s;
        cin>>s;
        ll k = 0;
        for(char c : s)
        {
            int ind = (int) c - (int) 'a';
            if(trie[k][ind] == -1)
            {
                trie[k][ind] = trie.size();
                mark.push_back(false);
                trie.push_back({});
                trie.back().assign(26, -1);
            }
            k = trie[k][ind];
        }
        mark[k] = true;
    }

    vector<ll> h(trie.size(), 0);
    preDFS(trie, 0, h);

    vector<char> output(0);
    dfs(mark, trie, output, 0, h);
    
    while(output.back() == '-')
        output.pop_back();
    cout<<output.size()<<"\n";
    for(char c : output)
        cout<<c<<"\n";
    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 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