oj.uz

Submission #222914

# Submission time Handle Problem Language Result Execution time Memory
222914 2020-04-14T10:44:50 Z miello Type Printer (IOI08_printer) C++11
100 / 100
 258 ms 101224 KB 
#include <bits/stdc++.h>

using namespace std;
const int MXN = 25005;

struct node {
    bool finalword = false , need = false;
    struct node* alpha[26];
    node() {
        for(int i = 0 ; i < 26 ; i++){
            this->alpha[i] = nullptr;
        }
    }
};

vector<char> ans;
vector<string> s;

void insert(node* now , string s , int idx , bool fin) {
    if(s.size() == idx) {
        now->need = true;
        return;
    }
    if(now->alpha[s[idx] - 'a'] == nullptr){
        now->alpha[s[idx] - 'a'] = new node();
        now->alpha[s[idx] - 'a']->finalword = fin;
    }
    insert(now->alpha[s[idx] - 'a'] , s , idx + 1 , fin);
}   

void dfs(node* now) {
    if(now->need) {
        ans.push_back('P');
    }
    for(int i = 0 ; i < 26 ; i++){
        if(now->alpha[i] != nullptr) {
            if(!now->alpha[i]->finalword) {
                ans.push_back('a' + i);
                dfs(now->alpha[i]);
                ans.push_back('-');
            }
        }
    }
    for(int i = 0 ; i < 26 ; i++){
        if(now->alpha[i] != nullptr) {
            if(now->alpha[i]->finalword) {
                ans.push_back('a' + i);
                dfs(now->alpha[i]);
            }
        }
    }
}

int main(){
    int n;
    scanf("%d" ,&n);
    for(int i = 0 ; i < n ; i++){
        string a;
        cin >> a;
        s.push_back(a);
    }
    sort(s.begin() , s.end() , [](string a , string b) {
        return a.size() > b.size();
    });
    node* root = new node();
    for(int i = 0 ; i < n ; i++) {
        if(i == 0) {
            insert(root, s[i], 0, true);
            continue;
        }
        insert(root, s[i], 0, false);
    }
    // printf("%d" ,root->alpha['p' - 'a']->alpha['r' - 'a']->finalword);
    dfs(root);
    printf("%d\n", ans.size());
    for(auto i : ans) {
        printf("%c\n" ,i);
    }
}

Compilation message

printer.cpp: In function 'void insert(node*, std::__cxx11::string, int, bool)':
printer.cpp:20:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(s.size() == idx) {
        ~~~~~~~~~^~~~~~
printer.cpp: In function 'int main()':
printer.cpp:75:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", ans.size());
                    ~~~~~~~~~~^
printer.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d" ,&n);
     ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 1152 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1920 KB Output is correct
2 Correct 9 ms 2304 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6144 KB Output is correct
2 Correct 37 ms 12788 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15308 KB Output is correct
2 Correct 32 ms 3960 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 37736 KB Output is correct
2 Correct 217 ms 85100 KB Output is correct
3 Correct 149 ms 45036 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 29928 KB Output is correct
2 Correct 258 ms 101224 KB Output is correct
3 Correct 168 ms 51048 KB Output is correct
4 Correct 251 ms 95716 KB Output is correct