oj.uz

Submission #501662

# Submission time Handle Problem Language Result Execution time Memory
501662 2022-01-04T09:23:40 Z 600Mihnea Type Printer (IOI08_printer) C++17
100 / 100
 137 ms 99584 KB 
#include <bits/stdc++.h>

using namespace std;

struct Node {
  Node* kids[26];
  int mxdep;
  bool we;
  Node() {
    for (int i = 0; i < 26; i++) {
      kids[i] = nullptr;
    }
    mxdep = 0;
    we = 0;
  }
};

int sn, ttl;
string sol;

void exp(Node* node) {
  if (node->we) {
    sol += "P";
    sn++;
  }
  if (sn == ttl) {
    cout << (int) sol.size() << "\n";
    for (auto &ch : sol) {
      cout << ch << "\n";
    }

    exit(0);
  }
  assert(node);
  int skip = -1;
  for (int j = 0; j < 26; j++) {
    if (node->kids[j]) {
      if (skip == -1 && node->kids[j]->mxdep + 1 == node->mxdep) {
        skip = j;
        continue;
      }
      sol += (char) ('a' + j);
      exp(node->kids[j]);
      sol += "-";
    }
  }
  if (skip != -1) {
    int j = skip;
    sol += (char) ('a' + j);
    exp(node->kids[j]);
    sol += "-";
  }
}

Node* root = new Node;

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  ///freopen ("input", "r", stdin);

  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    Node* current = root;
    int rem = (int) s.size();
    for (auto &ch : s) {
      int X = ch - 'a';
      current->mxdep = max(current->mxdep, rem--);
      assert(0 <= X && X < 26);
      if (!current->kids[X]) {
        current->kids[X] = new Node;
      }
      current = current->kids[X];
    }
    if (!current->we) ttl++;
    current->we = 1;
  }
  exp(root);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 312 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1728 KB Output is correct
2 Correct 3 ms 2252 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5916 KB Output is correct
2 Correct 16 ms 12488 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 14812 KB Output is correct
2 Correct 8 ms 3396 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 36640 KB Output is correct
2 Correct 118 ms 83728 KB Output is correct
3 Correct 61 ms 43136 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 28632 KB Output is correct
2 Correct 137 ms 99584 KB Output is correct
3 Correct 77 ms 48940 KB Output is correct
4 Correct 119 ms 94024 KB Output is correct