Submission #544565

#	Time	Username	Problem	Language	Result	Execution time	Memory
544565		DragosC1	Type Printer (IOI08_printer)	C++17	30 / 100	82 ms	21612 KiB

printer

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10