Submission #1220902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220902		kunzaZa183	Type Printer (IOI08_printer)	C++20	100 / 100	116 ms	75656 KiB

printer

#include <bits/stdc++.h>
using namespace std;
int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n;
  cin >> n;
  vector<string> vs(n);
  for (auto &a : vs)
    cin >> a;

  // const int letters = 26;
  struct node {
    map<char, int> mci;
    int ct = 0;
  };

  vector<node> vn;
  vn.emplace_back();

  for (auto &a : vs) {
    int in = 0;
    for (auto c : a) {
      if (!vn[in].mci.count(c)) {
        vn[in].mci[c] = vn.size();
        vn.emplace_back();
      }
      in = vn[in].mci[c];
    }
    vn[in].ct++;
  }

  vector<vector<pair<char, int>>> adj(vn.size());
  vector<int> dp(vn.size());
  for (int i = 0; i < vn.size(); i++) {
    for (auto a : vn[i].mci)
      adj[i].push_back(a);
  }

  function<int(int)> dfs = [&](int cur) {
    dp[cur] = 1;
    for (auto a : adj[cur])
      dp[cur] = max(dp[cur], dfs(a.second) + 1);
    return dp[cur];
  };
  dfs(0);

  for (int i = 0; i < vn.size(); i++) {
    sort(adj[i].begin(), adj[i].end(),
         [&](pair<char, int> a, pair<char, int> b) {
           return dp[a.second] < dp[b.second];
         });
  }

  string ans;

  int ct = 0;
  function<void(int)> dfs2 = [&](int cur) {
    if (vn[cur].ct) {
      ans.push_back('P');
      ct++;
      if (ct == n) {
        cout << ans.size() << "\n";
        for (auto a : ans)
          cout << a << "\n";
        exit(0);
      }
    }

    for (auto a : adj[cur]) {
      ans.push_back(a.first);
      dfs2(a.second);
      ans.push_back('-');
    }
  };
  dfs2(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