Submission #1176320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176320		qrq4	Type Printer (IOI08_printer)	C++20	100 / 100	172 ms	115248 KiB

printer

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define ld long double
#define ull unsigned long long
#define all(v) v.begin(), v.end()
#define point complex<ld>
#define QRQ4                    \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
const int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 1e6 + 5;
const ld pi = acos(-1);
const ld eps = 1e-9;
using namespace std;
using namespace __gnu_pbds;

int mx[N];
vector<char> ans;

struct Trie
{
  struct Node
  {
    int vis[26]{};
    int p = 0, en = 0;
  };

  vector<Node> tree;
  Trie() { tree.emplace_back(); }
  void insert(string s)
  {
    int idx = 0;
    for (auto &i : s)
    {
      int c = i - 'a';
      if (!tree[idx].vis[c])
      {
        tree[idx].vis[c] = tree.size();
        tree.emplace_back();
      }
      idx = tree[idx].vis[c];
      tree[idx].p++;
    }
    tree[idx].en++;
  }
  int query(string s)
  {
    int idx = 0;
    for (auto &i : s)
    {
      int c = i - 'a';
      if (!tree[idx].vis[c])
        return -1;
      idx = tree[idx].vis[c];
    }
    return tree[idx].p;
  }
};

void dfs(int node, int d, Trie &adj)
{
  mx[node] = d;
  for (int i = 0; i < 26; ++i)
  {
    if (!adj.tree[node].vis[i])
      continue;
    dfs(adj.tree[node].vis[i], d + 1, adj);
    mx[node] = max(mx[node], mx[adj.tree[node].vis[i]]);
  }
}

void dfs2(int node, Trie &adj)
{
  if (adj.tree[node].en)
    ans.push_back('P');
  for (int i = 0; i < 26; ++i)
  {
    if (!adj.tree[node].vis[i] or mx[node] == mx[adj.tree[node].vis[i]])
      continue;
    ans.push_back('a' + i);
    dfs2(adj.tree[node].vis[i], adj);
  }
  for (int i = 0; i < 26; ++i)
  {
    if (!adj.tree[node].vis[i] or mx[node] != mx[adj.tree[node].vis[i]])
      continue;
    ans.push_back('a' + i);
    dfs2(adj.tree[node].vis[i], adj);
  }
  ans.push_back('-');
}

void solve()
{
  int n;
  cin >> n;
  Trie trie;
  for (int i = 0; i < n; ++i)
  {
    string s;
    cin >> s;
    trie.insert(s);
  }
  dfs(0, 0, trie);
  dfs2(0, trie);
  while (ans.back() != 'P')
    ans.pop_back();
  cout << ans.size() << '\n';
  for (auto &it : ans)
    cout << it << '\n';
}

signed main()
{
  QRQ4
  int T = 1;
  // cin >> T;
  while (T--)
    solve();
  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