Submission #712540

#	Time	Username	Problem	Language	Result	Execution time	Memory
712540		caccaccac	Type Printer (IOI08_printer)	C++14	100 / 100	146 ms	99584 KiB

printer

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

struct TrieNode {
  TrieNode *child[26];
  bool end = 0;
  int max_h = 0;
  TrieNode() {
    for (int i = 0; i < 26; i++) {
      child[i] = NULL;
    }
    end = 0;
    max_h = 0;
  }
};

TrieNode *root = new TrieNode();

void add(string &s) {
  TrieNode *u = root;
  for (char ch : s) {
    ch -= 'a';
    if (u->child[ch] == NULL) {
      u->child[ch] = new TrieNode();
    }
    u = u->child[ch];
  }
  u->end = 1;
}

string f;

/**
 * minimize the minus in the end --> write the longest word in the end
 */

void dfs(TrieNode *u) {
  for (int i = 0; i < 26; i++) {
    if (u->child[i] != NULL) {
      dfs(u->child[i]);
      u->max_h = max(u->max_h, u->child[i]->max_h + 1);
    }
  }
}

void dfs_ans(TrieNode *u) {
  if (u->end) f += 'P';
  int longest = -1;
  for (int i = 0; i < 26; i++) {
    if (u->child[i] != NULL) {
      if (longest == -1) {
        longest = i;
      } else if (u->child[longest]->max_h < u->child[i]->max_h) {
        longest = i;
      }
    }
  }
  for (int i = 0; i < 26; i++) {
    if (longest == i) {
      continue;
    }
    if (u->child[i] != NULL) {
      f += char(i + 'a');
      dfs_ans(u->child[i]);
      f += '-';
    }
  }
  if (longest != -1) {
    f += char(longest + 'a');
    dfs_ans(u->child[longest]);
    f += '-';
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
#define task "a"
  if (fopen(task ".inp", "r")) {
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);
  }
  int n;
  cin >> n;
  while (n--) {
    string s;
    cin >> s;
    add(s);
  }
  dfs(root);
  dfs_ans(root);
  while (f.back() == '-') f.pop_back();
  cout << f.size() << "\n";
  for (char ch : f) cout << ch << "\n";
  return 0;
}

Compilation message (stderr)

printer.cpp: In function 'void add(std::string&)':
printer.cpp:23:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |     if (u->child[ch] == NULL) {
      |                  ^~
printer.cpp:24:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |       u->child[ch] = new TrieNode();
      |                ^~
printer.cpp:26:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |     u = u->child[ch];
      |                  ^~
printer.cpp: In function 'int main()':
printer.cpp:81:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:82:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• 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