oj.uz

Submission #1039120

# Submission time Handle Problem Language Result Execution time Memory
1039120 2024-07-30T13:13:15 Z Ludissey Type Printer (IOI08_printer) C++17
100 / 100
 235 ms 144204 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 3 ms 1672 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2652 KB Output is correct
2 Correct 6 ms 3160 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 8536 KB Output is correct
2 Correct 35 ms 18000 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 21328 KB Output is correct
2 Correct 43 ms 5460 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 53012 KB Output is correct
2 Correct 182 ms 121136 KB Output is correct
3 Correct 131 ms 63568 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 41696 KB Output is correct
2 Correct 235 ms 144204 KB Output is correct
3 Correct 204 ms 71948 KB Output is correct
4 Correct 210 ms 136264 KB Output is correct