oj.uz

Submission #1039123

# Submission time Handle Problem Language Result Execution time Memory
1039123 2024-07-30T13:14:38 Z Ludissey Type Printer (IOI08_printer) C++17
100 / 100
 149 ms 142792 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;
    }
    cout << sz(ops) << "\n";
    for (int i = sz(ops)-1; i >= 0; i--) {
        cout << ops[i] << "\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8540 KB Output is correct
2 Correct 23 ms 18012 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 21204 KB Output is correct
2 Correct 10 ms 5212 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 52428 KB Output is correct
2 Correct 129 ms 119888 KB Output is correct
3 Correct 70 ms 62660 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 41160 KB Output is correct
2 Correct 149 ms 142792 KB Output is correct
3 Correct 90 ms 71116 KB Output is correct
4 Correct 124 ms 134848 KB Output is correct