oj.uz

Submission #784855

# Submission time Handle Problem Language Result Execution time Memory
784855 2023-07-16T15:35:20 Z jakobrs Type Printer (IOI08_printer) C++17
100 / 100
 124 ms 105412 KB 
#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

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.0 / 10.0

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

Subtask #3
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 #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
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6228 KB Output is correct
2 Correct 17 ms 13132 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 15356 KB Output is correct
2 Correct 10 ms 3384 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 38516 KB Output is correct
2 Correct 105 ms 88588 KB Output is correct
3 Correct 65 ms 45552 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 30080 KB Output is correct
2 Correct 124 ms 105412 KB Output is correct
3 Correct 66 ms 51740 KB Output is correct
4 Correct 108 ms 99444 KB Output is correct