Submission #510076

#	Time	Username	Problem	Language	Result	Execution time	Memory
510076		BERNARB01	Type Printer (IOI08_printer)	C++17	100 / 100	236 ms	58292 KiB

printer

#include <bits/stdc++.h>

using namespace std;

vector<char> res;

struct trie {
  vector<array<int, 26>> T;
  vector<int> E, d, mxd;
  trie() {
    T.resize(1);
    E.resize(1);
    d.resize(1);
    mxd.resize(1);
  }
  void inserT(const string& s) {
    int t = 0;
    for (char c : s) {
      c -= 'a';
      if (!T[t][c]) {
        T[t][c] = T.size();
        T.emplace_back();
        E.emplace_back(0);
        d.push_back(0);
        mxd.push_back(0);
      }
      t = T[t][c];
    }
    E[t] += 1;
  }
  void dfs0(int t) {
    mxd[t] = d[t];
    for (int j = 0; j < 26; j++) {
      if (T[t][j]) {
        d[T[t][j]] = 1 + d[t];
        dfs0(T[t][j]);
        mxd[t] = max(mxd[t], mxd[T[t][j]]);
      }
    }
  }
  void DFS(int t) {
    vector<int> order(26);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int i, int j) {
      return mxd[T[t][i]] < mxd[T[t][j]];
    });
    for (int k = 0; k < E[t]; k++) {
      res.push_back('P');
    }
    for (int j : order) {
      if (T[t][j]) {
        res.push_back(char(j + 'a'));
        DFS(T[t][j]);
        res.push_back('-');
      }
    }
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  trie T;
  for (int i = 0; i < n; i++) {
    string foo;
    cin >> foo;
    T.inserT(foo);
  }
  T.dfs0(0);
  T.DFS(0);
  while (res.back() == '-') {
    res.pop_back();
    assert(!res.empty());
  }
  cout << res.size() << '\n';
  for (auto& x : res) {
    cout << x << '\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