oj.uz

Submission #1111187

# Submission time Handle Problem Language Result Execution time Memory
1111187 2024-11-11T16:31:20 Z pfv5068 Type Printer (IOI08_printer) C++14
100 / 100
 154 ms 96928 KB 
/*
  given a N words you have to minimize the number of operations, printing can be
  done in any order. Even if you have all words in a trie, how do you know from
  where to start and how to traverse it. where I'm stuck is: after storing words
  in trie, I found it is beneficial to print words that are near the parents
  first before going down the path, since we remove letters unnecessarily.

  if we assume the type printer should have no letters at the end, then the
  number of operations are equal, we can use dfs without worrying about the
  order.
*/
#include <cassert>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

// ToDo: create a Trie Iterator
using namespace std;
vector<char> container;
struct Trie {
  bool isEnd;
  unordered_map<char, Trie *> next;
  bool isSpecial;

public:
  Trie() : isEnd(false), isSpecial(false), next() {}
  Trie(const Trie &) = delete;
  Trie(Trie &&) = delete;

  void addWord(const string &word);
  bool searchWord(const string &word);
  void markNode(const string &word);
  void dfs();
};

// O(length(word)) * N
void Trie::addWord(const string &word) {
  Trie *curr = this;
  for (auto &ch : word) {
    auto it = curr->next.find(ch);
    if (it == curr->next.end()) {
      // create a new node.
      Trie *node = new Trie();
      curr->next[ch] = node;
    }
    curr = curr->next[ch];
  }
  curr->isEnd = true;
}

// O(length(word)) * N
bool Trie::searchWord(const string &word) {
  Trie *curr = this;
  for (auto &ch : word) {
    auto it = curr->next.find(ch);
    if (it == curr->next.end())
      return false;
    curr = it->second;
  }
  return curr->isEnd;
}

void Trie::markNode(const string &word) {
  Trie *curr = this;
  for (auto &ch : word) {
    auto it = curr->next.find(ch);
    if (it == curr->next.end())
      assert(false);
    curr = it->second;
    curr->isSpecial = true;
  }
}

void Trie::dfs() {
  unordered_map<char, Trie *>::iterator specialChild = next.end();
  if (isEnd)
    container.push_back('P');
  for (unordered_map<char, Trie *>::iterator it = next.begin();
       it != next.end(); it++) {
    if (it->second->isSpecial) {
      specialChild = it;
      continue;
    }
    container.push_back(it->first);
    it->second->dfs();
  }
  if (specialChild != next.end()) {
    container.push_back(specialChild->first);
    specialChild->second->dfs();
  }
  container.push_back('-');
}

int main() {
  Trie *root = new Trie();
  /*
  vector<const string> words{"canwatch", "watch", "prefix", "prefixOf"};

  for (auto const &ch : words)
    root->addWord(ch);

  for (auto const &ch : words)
    cout << root->searchWord(ch);
  cout << root->searchWord("canw");

  root->markNode("canwatch");
  root->dfs();
  */
  int n, len = 0;
  cin >> n;
  string word, bigword;
  while(n-- > 0) {
    cin >> word;
    root->addWord(word);
    if (word.size() > len) {
      len = word.size();
      bigword = word;
    }
  }
  root->markNode(bigword);
  root->dfs();

  while (container.back() != 'P')
    container.pop_back();

  cout << container.size();
  cout << "\n";
  for (auto &p : container)
    cout << p << "\n";
  return 0;
}

Compilation message

printer.cpp: In constructor 'Trie::Trie()':
printer.cpp:25:8: warning: 'Trie::isSpecial' will be initialized after [-Wreorder]
   25 |   bool isSpecial;
      |        ^~~~~~~~~
printer.cpp:24:31: warning:   'std::unordered_map<char, Trie*> Trie::next' [-Wreorder]
   24 |   unordered_map<char, Trie *> next;
      |                               ^~~~
printer.cpp:28:3: warning:   when initialized here [-Wreorder]
   28 |   Trie() : isEnd(false), isSpecial(false), next() {}
      |   ^~~~
printer.cpp: In function 'int main()':
printer.cpp:117:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  117 |     if (word.size() > len) {
      |         ~~~~~~~~~~~~^~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 1104 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1872 KB Output is correct
2 Correct 5 ms 2128 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5712 KB Output is correct
2 Correct 19 ms 11856 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 13772 KB Output is correct
2 Correct 11 ms 3408 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 34752 KB Output is correct
2 Correct 130 ms 81600 KB Output is correct
3 Correct 82 ms 40988 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 26020 KB Output is correct
2 Correct 154 ms 96928 KB Output is correct
3 Correct 98 ms 46396 KB Output is correct
4 Correct 154 ms 91328 KB Output is correct