Submission #881519

#	Time	Username	Problem	Language	Result	Execution time	Memory
881519		rxlfd314	Type Printer (IOI08_printer)	C++17	20 / 100	64 ms	44236 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 {
  int dep, mx;
  vt<DS*> ds;
  DS(int d) : ds(vt<DS*>(26, nullptr)), dep(d), mx(-1) {}
  void insert(string s, int i) {
    if (i == size(s))
      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) {
    FOR(i, 0, 25)
      if (ds[i] && (!special || i != mx)) {
        ans.push_back('a' + i);
        ds[i]->dfs2(ans, false);
        ans.push_back('-');
      }
    if (mx < 0)
      ans.push_back('P');
    else if (special) {
      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:17:11: warning: 'DS::ds' will be initialized after [-Wreorder]
   17 |   vt<DS*> ds;
      |           ^~
printer.cpp:16:7: warning:   'int DS::dep' [-Wreorder]
   16 |   int dep, mx;
      |       ^~~
printer.cpp:18:3: warning:   when initialized here [-Wreorder]
   18 |   DS(int d) : ds(vt<DS*>(26, nullptr)), dep(d), mx(-1) {}
      |   ^~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10