Submission #1077565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077565		juicy	Type Printer (IOI08_printer)	C++17	100 / 100	94 ms	52816 KiB

printer

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int MAX = 500005, C = 26;

int node;
int dep[MAX], ind[MAX], ma[MAX];
bool flg[MAX];
array<int, C> nxt[MAX];

void add(string s) {
  int p = 0;
  for (char c : s) {
    if (!nxt[p][c - 'a']) {
      nxt[p][c - 'a'] = ++node;
    }
    p = nxt[p][c - 'a'];
  }
  flg[p] = 1;
}

void dfs(int u) {
  ma[u] = dep[u];
  ind[u] = u;
  for (int v : nxt[u]) {
    if (v) {
      dep[v] = dep[u] + 1;
      dfs(v);
      if (ma[v] > ma[u]) {
        ma[u] = ma[v];
        ind[u] = v;
      }
    }
  }
}

void dfs(int u, bool keep) {
  if (flg[u]) {
    cout << "P" << "\n";
  }
  char s;
  for (int i = 0; i < C; ++i) {
    int v = nxt[u][i];
    if (v && v != ind[u]) {
      cout << char(i + 'a') << "\n";
      dfs(v, 0);
    } else if (v == ind[u]) {
      s = i + 'a';
    }
  }
  if (ind[u] ^ u) {
    cout << s << "\n";
    dfs(ind[u], keep);
  }
  if (!keep) {
    cout << "-" << "\n";
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int n; cin >> n;
  for (int i = 0; i < n; ++i) {
    string s; cin >> s;
    add(s);
  }
  dfs(0);
  cout << 2 * node + n - ma[0] << "\n";
  dfs(0, 1);
  return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void dfs(int, bool)':
printer.cpp:48:8: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |   char s;
      |        ^

• 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