oj.uz

Submission #652567

# Submission time Handle Problem Language Result Execution time Memory
652567 2022-10-23T07:11:07 Z alvinpiter Type Printer (IOI08_printer) C++17
100 / 100
 109 ms 56764 KB 
/*
* Insert each word into a trie
* "Add" operation is the same as going an edge downward, while "Remove" operation is the same as
  going an edge upward. If there is a requirement that the printer must be empty after all operations
  are performed, then the answer is 2 * numberOfEdgesInTheTrie + numberOfWords.
* However, we are allowed to leave some letters in the printer, so it is best if we leave the longest word in
  the printer.
*/

#include<bits/stdc++.h>
using namespace std;
#define MAX_NODE 500000

int numberOfNodesInTrie = 1; // Root is numbered 1
int trie[MAX_NODE + 3][26], maxDepth[MAX_NODE + 3];
bool isEndOfAWord[MAX_NODE + 3];

vector<char> result;

void insert(string s) {
  int currentNode = 1;
  for (int i = 0; i < s.length(); i++) {
    int charIndex = (s[i] - 'a');

    maxDepth[currentNode] = max(maxDepth[currentNode], (int) s.length() - i);
    if (trie[currentNode][charIndex] == -1) {
      trie[currentNode][charIndex] = ++numberOfNodesInTrie;
    }

    currentNode = trie[currentNode][charIndex];
  }

  isEndOfAWord[currentNode] = true;
}

void traverse(int currentNode) {
  if (isEndOfAWord[currentNode]) {
    result.push_back('P');
  }

  int deepestChildIdx = -1;
  for (int i = 0; i < 26; i++) {
    if (trie[currentNode][i] != -1 && (deepestChildIdx == -1 || maxDepth[trie[currentNode][i]] > maxDepth[trie[currentNode][deepestChildIdx]])) {
      deepestChildIdx = i;
    }
  }

  for (int i = 0; i < 26; i++) {
    if (trie[currentNode][i] != -1 && i != deepestChildIdx) {
      result.push_back((char) (i + 'a'));
      traverse(trie[currentNode][i]);
    }
  }

  if (deepestChildIdx != -1) {
    result.push_back((char) (deepestChildIdx + 'a'));
    traverse(trie[currentNode][deepestChildIdx]);
  }

  result.push_back('-');
}

int main() {
  int n;
  scanf("%d", &n);

  memset(trie, -1, sizeof(trie));
  memset(maxDepth, 0, sizeof(maxDepth));
  memset(isEndOfAWord, false, sizeof(isEndOfAWord));
  for (int i = 0; i < n; i++) {
    char s[25];
    scanf("%s", s);

    string w(s);

    insert(w);
  }

  traverse(1);

  while (result.back() == '-') {
    result.pop_back();
  }

  printf("%d\n", (int) result.size());
  for (auto r: result) {
    printf("%c\n", r);
  }
}

Compilation message

printer.cpp: In function 'void insert(std::string)':
printer.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for (int i = 0; i < s.length(); i++) {
      |                   ~~^~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
printer.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%s", s);
      |     ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 53580 KB Output is correct
2 Correct 21 ms 53564 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53500 KB Output is correct
2 Correct 23 ms 53588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 53516 KB Output is correct
2 Correct 24 ms 53536 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 53568 KB Output is correct
2 Correct 22 ms 53588 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 53588 KB Output is correct
2 Correct 22 ms 53540 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 53588 KB Output is correct
2 Correct 25 ms 53588 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 53824 KB Output is correct
2 Correct 36 ms 53988 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 54096 KB Output is correct
2 Correct 31 ms 53708 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 54704 KB Output is correct
2 Correct 89 ms 55996 KB Output is correct
3 Correct 67 ms 54904 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 54468 KB Output is correct
2 Correct 109 ms 56428 KB Output is correct
3 Correct 62 ms 55568 KB Output is correct
4 Correct 90 ms 56764 KB Output is correct