oj.uz

Submission #544567

# Submission time Handle Problem Language Result Execution time Memory
544567 2022-04-02T11:16:56 Z DragosC1 Type Printer (IOI08_printer) C++17
100 / 100
 162 ms 58380 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');
    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('-');
    }
}

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:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (i = 0; i < rez.size(); i++)
      |                 ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1108 KB Output is correct
2 Correct 4 ms 1364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3564 KB Output is correct
2 Correct 24 ms 7456 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 8668 KB Output is correct
2 Correct 14 ms 2132 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 21316 KB Output is correct
2 Correct 142 ms 49128 KB Output is correct
3 Correct 99 ms 25444 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 16740 KB Output is correct
2 Correct 162 ms 58380 KB Output is correct
3 Correct 115 ms 28904 KB Output is correct
4 Correct 133 ms 55192 KB Output is correct