Submission #881522

#	Time	Username	Problem	Language	Result	Execution time	Memory
881522		rxlfd314	Type Printer (IOI08_printer)	C++17	100 / 100	195 ms	119964 KiB

printer

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

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) (a = max(1ll * a, 1ll * (b)))
#define chmin(a, b) (a = min(1ll * a, 1ll * (b)))

struct DS {
  bool yes;
  int dep, mx;
  vt<DS*> ds;
  DS(int d) : ds(vt<DS*>(26, nullptr)), dep(d), mx(-1), yes(false) {}
  void insert(string &s, int i) {
    if (i == size(s)) {
      yes = true;
      return;
    }
    if (!ds[s[i]-'a'])
      ds[s[i]-'a'] = new DS(dep+1);
    ds[s[i]-'a']->insert(s, i+1);
  }
  void dfs1() {
    FOR(i, 0, 25)
      if (ds[i]) {
        ds[i]->dfs1();
        if (ds[i]->dep > dep)
          dep = ds[i]->dep, mx = i;
      }
  }
  void dfs2(vt<char> &ans, bool special) {
    if (yes)
      ans.push_back('P');
    FOR(i, 0, 25)
      if (ds[i] && (!special || i != mx)) {
        ans.push_back('a' + i);
        ds[i]->dfs2(ans, false);
        ans.push_back('-');
      }
    if (special && ~mx) {
      ans.push_back('a' + mx);
      ds[mx]->dfs2(ans, true);
    }
  }
};

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  DS *ds = new DS(0);
  FOR(_, 1, N) {
    string s;
    cin >> s;
    ds->insert(s, 0);
  }
  vt<char> ans;
  ds->dfs1();
  ds->dfs2(ans, true);
  cout << size(ans) << '\n';
  for (char c : ans)
    cout << c << '\n';
}

Compilation message (stderr)

printer.cpp: In constructor 'DS::DS(int)':
printer.cpp:18:11: warning: 'DS::ds' will be initialized after [-Wreorder]
   18 |   vt<DS*> ds;
      |           ^~
printer.cpp:17:7: warning:   'int DS::dep' [-Wreorder]
   17 |   int dep, mx;
      |       ^~~
printer.cpp:19:3: warning:   when initialized here [-Wreorder]
   19 |   DS(int d) : ds(vt<DS*>(26, nullptr)), dep(d), mx(-1), yes(false) {}
      |   ^~
printer.cpp:17:12: warning: 'DS::mx' will be initialized after [-Wreorder]
   17 |   int dep, mx;
      |            ^~
printer.cpp:16:8: warning:   'bool DS::yes' [-Wreorder]
   16 |   bool yes;
      |        ^~~
printer.cpp:19:3: warning:   when initialized here [-Wreorder]
   19 |   DS(int d) : ds(vt<DS*>(26, nullptr)), dep(d), mx(-1), yes(false) {}
      |   ^~

• 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