제출 #1260178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1260178		Born_To_Laugh	Type Printer (IOI08_printer)	C++17	100 / 100	115 ms	60012 KiB

printer

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
vector<char> ans;
string a;
struct Prefix_Trie
{
    int n;
    struct node {
        int exist = 0;
        int disttoleaf = 1;
        int lovchi = 0;
        array<int, 26> child;
    };
    vector<node> tree;
    int id = 0;
    Prefix_Trie(){
        tree.push_back(node());
    }
    int newnode(){
        id++;
        tree.push_back(node());
        return id;
    }

    void insert(string & a){
        int pos = 0;
        for(auto &elm: a){
            int val = elm - 'a';
            if(!tree[pos].child[val])tree[pos].child[val] = newnode();
            pos = tree[pos].child[val];
        }
        tree[pos].exist++;
    }
    void distcompute(int pos){
        for(int i=0; i<26; ++i){
            if(!tree[pos].child[i])continue;
            distcompute(tree[pos].child[i]);
            
            int nxt = tree[pos].child[i];
            if(tree[nxt].disttoleaf + 1 > tree[pos].disttoleaf){
                tree[pos].lovchi = nxt;
                tree[pos].disttoleaf = tree[nxt].disttoleaf + 1;
            }
        }
    }
    void dfs(int pos){
        int savesz = a.size();
        if(tree[pos].exist){
            ans.push_back('P');
        }
        int j = -1;
        for(int i=0; i<26; ++i){
            if(!tree[pos].child[i])continue;
            int nxt = tree[pos].child[i];
            if(nxt == tree[pos].lovchi){
                j = i;
                continue;
            }

            a.push_back(char('a' + i));
            // cout << a << '\n';
            ans.push_back(char('a' + i));
            dfs(nxt);
            while(a.size() != savesz){
                a.pop_back();
                ans.push_back('-');
            }
        } 
        if(j != -1){
            a.push_back(char('a' + j));
            ans.push_back(char('a' + j));
            dfs(tree[pos].lovchi);
        }
    }
};
Prefix_Trie trie;
void solve(){
    int n;cin >> n;
    for(int i=1; i<=n; ++i){
        string a;cin >> a;
        trie.insert(a);
    }
    trie.distcompute(0);
    trie.dfs(0);
    cout << ans.size() << '\n';
    for(auto &elm: ans)cout << elm << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

• 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