Submission #1118592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118592		anuj_anand	Type Printer (IOI08_printer)	C++17	100 / 100	176 ms	65820 KiB

printer

#include <bits/stdc++.h>
using namespace std;

/*
*/

using i64 = long long;
const int MOD = 1e9 + 7;

const int K = 26;
struct Vertex {
  vector <int> nxt;
  int ends;
  int max_dep;
  Vertex() : ends{0}, nxt(26, 0), max_dep{0} {}
  void depth(int x) {
    max_dep = max(max_dep, x);
  }
};
vector <Vertex> Trie (1);

void solve() {
  int n;
  cin >> n;

  int root = 0;
  auto insert = [&] (string &s) -> void {
    int node = root;
    int n = s.size();
    for (int i = 0; i < n; ++i) {
      if (Trie[node].nxt[s[i] - 'a'] == 0) {
        Trie[node].nxt[s[i] - 'a'] = Trie.size();
        Trie.push_back(Vertex());
      }
      node = Trie[node].nxt[s[i] - 'a'];
      Trie[node].depth(n - i);
    }
    Trie[node].ends += 1;
  };

  int mx = 0;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    insert(s);
    mx = max(mx, (int) s.size());
  }

  vector <char> res;
  auto dfs = [&] (auto &&dfs, int root) -> void {
    if (Trie[root].ends) {
      for (int tim = 0; tim < Trie[root].ends; tim++) { res.push_back('P'); }
    }
    int maxi = -1;
    int spc = -1;
    for (int c = 0; c < K; ++c) {
      int dep = Trie[Trie[root].nxt[c]].max_dep;
      if (dep > maxi) {
        maxi = dep;
        spc = c;
      }
    }
    for (int c = 0; c < K; ++c) if (c != spc) {
      int v = Trie[root].nxt[c];
      if (v != 0) { res.push_back(c + 'a'); dfs(dfs, v); res.push_back('-'); }
    }
    if (spc != -1 and Trie[root].nxt[spc] != 0) {
      res.push_back(spc + 'a');
      dfs(dfs, Trie[root].nxt[spc]);
      res.push_back('-');
    }
  };

  dfs(dfs, 0);

  while (mx--) { res.pop_back(); }

  cout << res.size() << "\n";
  for (char x : res) {
    cout << x << "\n";
  }
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int tests = 1;
  // cin >> tests;
  for (int test = 0; test < tests; ++test) {
    solve();
  }
  return 0;
}

Compilation message (stderr)

printer.cpp: In constructor 'Vertex::Vertex()':
printer.cpp:13:7: warning: 'Vertex::ends' will be initialized after [-Wreorder]
   13 |   int ends;
      |       ^~~~
printer.cpp:12:16: warning:   'std::vector<int> Vertex::nxt' [-Wreorder]
   12 |   vector <int> nxt;
      |                ^~~
printer.cpp:15:3: warning:   when initialized here [-Wreorder]
   15 |   Vertex() : ends{0}, nxt(26, 0), max_dep{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