Submission #784855

#	Time	Username	Problem	Language	Result	Execution time	Memory
784855		jakobrs	Type Printer (IOI08_printer)	C++17	100 / 100	124 ms	105412 KiB

printer

#include <iostream>

using i64 = int64_t;

struct Node {
  Node *children[26];
  bool is_terminal = false;

  i64 longest = 0;
  i64 go_here_last = -1;

  Node() { std::fill(std::begin(children), std::end(children), nullptr); }
};

void dfs(Node *node, i64 &w) {
  if (node->is_terminal) {
    std::cout << "P\n";
    w--;
  }

  for (i64 i = 0; i < 26; i++) {
    if (i != node->go_here_last && node->children[i]) {
      std::cout << (char)(i + 'a') << '\n';
      dfs(node->children[i], w);
      if (w)
        std::cout << "-\n";
    }
  }

  if (node->go_here_last != -1) {
    std::cout << (char)(node->go_here_last + 'a') << '\n';
    dfs(node->children[node->go_here_last], w);
    if (w)
      std::cout << "-\n";
  }
}
int main() {
  i64 n;
  std::cin >> n;

  Node root;
  i64 op_count = 0;

  std::string word;
  for (i64 i = 0; i < n; i++) {
    word.clear();
    std::cin >> word;

    Node *cur = &root;
    for (char ch : word) {
      if (word.size() > cur->longest) {
        cur->go_here_last = ch - 'a';
        cur->longest = word.size();
      }
      if (!cur->children[ch - 'a']) {
        cur->children[ch - 'a'] = new Node();
        op_count += 2;
      }
      cur = cur->children[ch - 'a'];
    }

    cur->is_terminal = true;
    op_count += 1;
  }

  op_count -= root.longest;
  std::cout << op_count << '\n';
  i64 w = n;
  dfs(&root, w);
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:51:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'i64' {aka 'long int'} [-Wsign-compare]
   51 |       if (word.size() > cur->longest) {
      |           ~~~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10