oj.uz

Submission #235618

# Submission time Handle Problem Language Result Execution time Memory
235618 2020-05-28T20:28:55 Z Haunted_Cpp Type Printer (IOI08_printer) C++17
100 / 100
 199 ms 99696 KB 
/**
 *  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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 416 KB Output is correct
2 Correct 6 ms 1152 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1920 KB Output is correct
2 Correct 8 ms 2304 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6016 KB Output is correct
2 Correct 32 ms 12664 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14712 KB Output is correct
2 Correct 14 ms 3456 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 36468 KB Output is correct
2 Correct 173 ms 83432 KB Output is correct
3 Correct 89 ms 42864 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 28660 KB Output is correct
2 Correct 199 ms 99696 KB Output is correct
3 Correct 100 ms 49140 KB Output is correct
4 Correct 172 ms 94188 KB Output is correct