Submission #235618

#	Time	Username	Problem	Language	Result	Execution time	Memory
235618		Haunted_Cpp	Type Printer (IOI08_printer)	C++17	100 / 100	199 ms	99696 KiB

printer

/**
 *  author: Duarte Nobrega
 *  created: 28.05.2020    
**/

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

struct Node {
  Node *abc[26] = {nullptr};
  int sub = 0;
  bool is_word = false;
} *root, *cur;

void inserir (const string &w) {
  cur = root;
  for (int i = 0; i < (int) w.size(); i++) {
    if (cur -> abc[w[i] - 'a'] == nullptr) {
      cur -> abc[w[i] - 'a'] = new Node;
    }
    cur = cur -> abc[w[i] - 'a'];
  }
  cur -> is_word = true;
}

vector<char> ans;

void dfs (Node *current) {
  if (current -> is_word) ans.emplace_back('P');
  vector< pair<int, int> > ordem;
  for (int i = 0; i < 26; i++) {
    if (current -> abc[i] != nullptr) {
      ordem.emplace_back( current -> abc[i] -> sub, i );
    }
  }
  sort (ordem.begin(), ordem.end());
  for (auto to : ordem) {
    ans.emplace_back(char ('a' + to.second));
    dfs (current -> abc[to.second]);
  }
  ans.emplace_back('-');
}

int get_size (Node *current) {
  int res = 0;
  for (int i = 0; i < 26; i++) {
    if (current -> abc[i] != nullptr) {
      res = max (res, get_size (current -> abc[i]));
    }
  }
  return current -> sub = res + 1;
}

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  root = new Node;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string w;
    cin >> w;
    inserir (w);
  }
  get_size (root);
  dfs (root);
  while (ans.back() == '-') ans.pop_back();
  cout << (int) ans.size() << '\n';
  for (auto to : ans) cout << to << '\n';
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10