oj.uz

Submission #712540

# Submission time Handle Problem Language Result Execution time Memory
712540 2023-03-19T06:20:57 Z caccaccac Type Printer (IOI08_printer) C++14
100 / 100
 146 ms 99584 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1748 KB Output is correct
2 Correct 3 ms 2260 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5972 KB Output is correct
2 Correct 34 ms 12492 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14684 KB Output is correct
2 Correct 8 ms 3412 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 36452 KB Output is correct
2 Correct 123 ms 83692 KB Output is correct
3 Correct 66 ms 43116 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 28392 KB Output is correct
2 Correct 146 ms 99584 KB Output is correct
3 Correct 85 ms 48988 KB Output is correct
4 Correct 128 ms 94004 KB Output is correct