oj.uz

Submission #652555

# Submission time Handle Problem Language Result Execution time Memory
652555 2022-10-23T06:33:59 Z alvinpiter Type Printer (IOI08_printer) C++17
30 / 100
 475 ms 36604 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;

struct TrieNode {
  int maxDepth;
  bool isEndOfAWord;
  TrieNode* children[26];

  TrieNode(int maxDepth_ = 0, bool isEndOfAWord_ = false): maxDepth(maxDepth_), isEndOfAWord(isEndOfAWord_) {}
};

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

    currentNode->maxDepth = max(currentNode->maxDepth, (int) s.length() - i);
    if (currentNode->children[charIndex] == NULL) {
      TrieNode* newNode = new TrieNode(s.length() - i - 1, i == (s.length() - 1));
      currentNode->children[charIndex] = newNode;
    }

    currentNode = currentNode->children[charIndex];
  }
}

void traverse(TrieNode* root, vector<char>& result) {
  if (root->isEndOfAWord) {
    result.push_back('P');
  }

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

  for (int i = 0; i < 26; i++) {
    if (root->children[i] != NULL && i != deepestChildIdx) {
      result.push_back((char) (i + 'a'));
      traverse(root->children[i], result);
    }
  }

  if (deepestChildIdx != -1) {
    result.push_back((char) (deepestChildIdx + 'a'));
    traverse(root->children[deepestChildIdx], result);
  }

  result.push_back('-');
}

int main() {
  int n;
  cin >> n;

  TrieNode* trieRoot = new TrieNode();
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;

    insert(trieRoot, s);
  }

  vector<char> result;
  traverse(trieRoot, result);

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

  cout << result.size() << endl;
  for (auto r: result) {
    cout << r << endl;
  }
}

Compilation message

printer.cpp: In function 'void insert(TrieNode*, std::string)':
printer.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for (int i = 0; i < s.length(); i++) {
      |                   ~~^~~~~~~~~~~~
printer.cpp:28:62: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |       TrieNode* newNode = new TrieNode(s.length() - i - 1, i == (s.length() - 1));
      |                                                            ~~^~~~~~~~~~~~~~~~~~~

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

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 296 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 1748 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 5896 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 170 ms 14728 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 475 ms 36604 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 367 ms 28560 KB didn't print every word
2 Halted 0 ms 0 KB -