Submission #501662

#	Time	Username	Problem	Language	Result	Execution time	Memory
501662		600Mihnea	Type Printer (IOI08_printer)	C++17	100 / 100	137 ms	99584 KiB

printer

#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 / 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