oj.uz

Submission #544565

# Submission time Handle Problem Language Result Execution time Memory
544565 2022-04-02T11:15:56 Z DragosC1 Type Printer (IOI08_printer) C++17
30 / 100
 82 ms 21612 KB 
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;

struct trie {
    bool cuv;
    int down;
    map<int, trie*> lit;
    trie() {
        cuv = down = 0;
    }
};

trie *root;
string s;

void add(trie *node, int ind) {
    if (ind == s.size()) {
        node->cuv = 1;
        return;
    }
    int l = s[ind] - 'a';
    if (node->lit[l] == NULL)
        node->lit[l] = new trie();
    add(node->lit[l], ind + 1);
    node->down = max(node->down, node->lit[l]->down + 1);
}

string rez;

void dfs(trie *node) {
    if (node->cuv == 1)
        rez.push_back('P');
    if (node == root) {
        vector<pair<int, char>> v;
        for (auto it = node->lit.begin(); it != node->lit.end(); it++)
            v.push_back({node->lit[it->first]->down, it->first});
        sort(v.begin(), v.end());
        for (int i = 0; i < v.size(); i++) {
            rez.push_back(v[i].second + 'a');
            dfs(node->lit[v[i].second]);
            rez.push_back('-');
        }
    }
    else
        for (auto it = node->lit.begin(); it != node->lit.end(); it++) {
            rez.push_back(it->first + 'a');
            dfs(node->lit[it->first]);
            rez.push_back('-');
        }
}

int main() {
    root = new trie();
    int i, n;
    cin >> n;
    for (i = 1; i <= n; i++) {
        cin >> s;
        add(root, 0);
    }
    dfs(root);
    while (rez.back() == '-')
        rez.pop_back();
    cout << rez.size() << '\n';
    for (i = 0; i < rez.size(); i++)
        cout << rez[i] << '\n';
    return 0;
}

Compilation message

printer.cpp: In constructor 'trie::trie()':
printer.cpp:12:20: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   12 |         cuv = down = 0;
      |               ~~~~~^~~
printer.cpp: In function 'void add(trie*, int)':
printer.cpp:20:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     if (ind == s.size()) {
      |         ~~~~^~~~~~~~~~~
printer.cpp: In function 'void dfs(trie*)':
printer.cpp:41:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for (int i = 0; i < v.size(); i++) {
      |                         ~~^~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (i = 0; i < rez.size(); i++)
      |                 ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3540 KB Output is correct
2 Incorrect 21 ms 7480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 8804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 21612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 16912 KB Output isn't correct
2 Halted 0 ms 0 KB -