Submission #1039120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039120		Ludissey	Type Printer (IOI08_printer)	C++17	100 / 100	235 ms	144204 KiB

printer

#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()

using namespace std;


struct trie{
    char c;
    trie* child[27];
    vector<bool> visited;
    bool isEND=0;
    trie* parent;
    trie(trie* root, char _c){
        for (int i = 0; i < 27; i++) child[i]=nullptr;
        this->visited.resize(27,0);
        isEND=false;
        c=_c;
        parent=root;
    }
};

void add(trie* root, string s, int i){
    if(i==sz(s)) { root->isEND=true; return; }
    if(root->child[s[i]-'a']==nullptr) root->child[s[i]-'a']=new trie(root,s[i]);
    add(root->child[s[i]-'a'],s,i+1);
}

trie* find_lowest_trie(trie* root, string s, int i){
    if(i==sz(s)) return root;
    return find_lowest_trie(root->child[s[i]-'a'],s,i+1);
}

void remove_exist(trie* root ,int last){
    if(root->c==' ') return;
    for (int i = 0; i < 27; i++) {
         if(root->child[i]!=nullptr&&i!=last) return;
    }
    int nl=root->c-'a';
    root->parent->visited[nl]=true;
    remove_exist(root->parent,nl);
}

vector<char> ops;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<string> a(N);
    trie* root=new trie(nullptr,' '); 
    for (int i = 0; i < N; i++) cin >> a[i];
    for (int i = 0; i < N; i++) add(root,a[i],0);
    sort(all(a), [](string &_a, string &b){return sz(_a)<sz(b);});
    trie* current=find_lowest_trie(root, a[N-1], 0);
    remove_exist(current,-1);
    while(true){
        bool b=true;
        for (int i=0; i<27; i++)
        {
            if(current->child[i]==nullptr||current->visited[i]) continue;
            current->visited[i]=true;
            current=current->child[i];
            ops.push_back('-');
            b=false;
        }
        if(b) {
            if(current->c==' ') break;
            else {
                current->parent->visited[current->c-'a']=true;
                if(current->isEND) { ops.push_back('P'); current->isEND=false; }
                ops.push_back(current->c);
                current=current->parent;
            }
        } else continue;
    }
    vector<char> ops2;
    for (int i = sz(ops)-1; i >= 0; i--) {
        ops2.push_back(ops[i]);
    }
    string s="";
    cout << sz(ops2) << "\n";
    for (int i = 0; i < sz(ops2); i++) {
        if(ops2[i]=='-') s.erase(sz(s)-1);
        else if(ops2[i]=='P') cerr<<s<<"\n";
        else s+=ops2[i];
        cout << ops2[i] << "\n";
    }
    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