oj.uz

Submission #235613

# Submission time Handle Problem Language Result Execution time Memory
235613 2020-05-28T20:09:18 Z Haunted_Cpp Type Printer (IOI08_printer) C++17
30 / 100
 159 ms 83820 KB 
/**
 *  author: Duarte Nobrega
 *  created: 28.05.2020    
**/

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

struct Node {
  Node *abc[26];
  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 = 1;
  for (int i = 0; i < 26; i++) {
    if (current -> abc[i] != nullptr) {
      res += get_size (current -> abc[i]);
    }
  }
  current -> sub = res;
  return res;
}

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

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
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 #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1920 KB Output is correct
2 Incorrect 8 ms 2304 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 6016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 14848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 36700 KB Output is correct
2 Correct 159 ms 83820 KB Output is correct
3 Incorrect 86 ms 43248 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 28788 KB Output isn't correct
2 Halted 0 ms 0 KB -