oj.uz

Submission #521592

# Submission time Handle Problem Language Result Execution time Memory
521592 2022-02-02T13:55:42 Z vlad_TT Type Printer (IOI08_printer) C++17
0 / 100
 57 ms 76448 KB 
#include <iostream>
#include <cstring>

const int SIGMA = 26;

struct Trie {
  int words;
  Trie* children[SIGMA];
  bool is_ancestor;

  Trie() {
    words = 0;
    is_ancestor = false;
    for (int i = 0; i < SIGMA; i++) {
      children[i] = NULL;
    }
  }
};

void insert(Trie* root, char* S) {
  if (*S == '\0') {
    root->words++;
  } else {
    if (root->children[S[0] - 'a'] == NULL) {
      root->children[S[0] - 'a'] = new Trie();
    }
    insert(root->children[S[0] - 'a'], S + 1);
  }
}

void stramosi(Trie* root, char* S) {
  if (*S != '\0') {
    root->children[S[0] - 'a']->is_ancestor = true;
    stramosi(root->children[S[0] - 'a'], S + 1);
  }
}

int answer = 0;

int count(Trie* root) {
  answer += root->words;
  for (int i = 0; i < SIGMA; i++) {
    if (root->children[i] != NULL && root->children[i]->is_ancestor == false) {
      answer++;
      count(root->children[i]);
      answer++;
    }
  }
  for (int i = 0; i < SIGMA; i++) {
    if (root->children[i] != NULL && root->children[i]->is_ancestor == true) {
      answer++;
      count(root->children[i]);
    }
  }
}

void dfs(Trie* root) {
  for (int i = 1; i <= root->words; i++) {
    std::cout << "P\n";
  }
  for (int i = 0; i < SIGMA; i++) {
    if (root->children[i] != NULL && root->children[i]->is_ancestor == false) {
      std::cout << char(i + 'a') << "\n";
      dfs(root->children[i]);
      std::cout << "-\n";
    }
  }
  for (int i = 0; i < SIGMA; i++) {
    if (root->children[i] != NULL && root->children[i]->is_ancestor == true) {
      std::cout << char(i + 'a') << "\n";
      dfs(root->children[i]);
    }
  }
}

int main() {
  Trie root;
  char* S = new char[20 + 1];
  char last[20 + 1];
  int n, mx = 0;
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    std::cin >> S;
    if (strlen(S) > mx) {
      mx = strlen(S);
      for (int j = 0; S[j] != '\0'; j++) {
        last[j] = S[j];
      }
    }
    insert(&root, S);
  }
  char c;
  c = std::cin.get();
  if (c == ' ') {
    c = std::cin.get();
  }
  stramosi(&root, last);
  count(&root);
  std::cout << answer << "\n";
  dfs(&root);
  return 0;
}

Compilation message

printer.cpp: In function 'int count(Trie*)':
printer.cpp:55:1: warning: no return statement in function returning non-void [-Wreturn-type]
   55 | }
      | ^
printer.cpp: In function 'int main()':
printer.cpp:84:19: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |     if (strlen(S) > mx) {
      |         ~~~~~~~~~~^~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 332 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 396 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 588 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 3532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 12156 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 30412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 76448 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 53 ms 59460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -