Submission #557926

#	Time	Username	Problem	Language	Result	Execution time	Memory
557926		Soumya1	Type Printer (IOI08_printer)	C++17	100 / 100	149 ms	59188 KiB

printer

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int alpha = 26;
const int mxN = 25005;
const int mxSize = 21;
int to[mxN * mxSize][alpha];
bool e[mxN * mxSize];
int d[mxN * mxSize];
int root;
int cnt;
string ans;
void insert(string s) {
  int cur = root;
  for (char c : s) {
    int id = c - 'a';
    if (to[cur][id] == -1) {
      to[cur][id] = ++cnt;
    }
    cur = to[cur][id];
  }
  e[cur] = true;
}
void calc_d(int u) {
  for (int i = 0; i < alpha; i++) {
    int v = to[u][i];
    if (v == -1) continue;
    calc_d(v);
    d[u] = max(d[u], d[v] + 1);
  }
}
void dfs(int u, bool go, char c) {
  if (u) ans += c;
  if (e[u]) ans += 'P';
  pair<int, int> ret = {-1, -1};
  for (int i = 0; i < alpha; i++) {
    int v = to[u][i];
    if (v != -1) {
      ret = max(ret, {d[v], i});
    }
  }
  for (int i = 0; i < alpha; i++) {
    int v = to[u][i];
    if (v == -1) continue;
    if (!go || ret.second != i) {
      dfs(v, false, i + 'a');
    }
  }
  if (go && ret.first != -1) dfs(to[u][ret.second], true, ret.second + 'a');
  if (!go) ans += '-';
}
void testCase() {
  memset(to, -1, sizeof to);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    insert(s);
  }
  calc_d(0);
  dfs(0, true, ' ');
  cout << ans.size() << "\n";
  for (char c : ans) {
    cout << c << "\n";
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  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