oj.uz

Submission #712539

# Submission time Handle Problem Language Result Execution time Memory
712539 2023-03-19T06:20:24 Z caccaccac Type Printer (IOI08_printer) C++14
0 / 100
 62 ms 36040 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";
  cout << f;
  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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Line "tptttykduyvxjbzhqupP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Line "eejzatjmnqxctnP--------------h...-yerxP----labfaryosskugbkiuffdP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Line "hjxgqkP------iupqiqP------rhpq...------------wPfxlmwfirlgbdevjdP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Line "bhvdxrpthaP----------edczvdgoy...--------------xomsgennpdlurnmvP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Line "aedP--svhblhtkqjP----------bbb...----ooP--ulwzP----eynorwrbizaiP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1748 KB Line "aPaisxlhagqbjwbP-------------b...----------zP-cclviwgdudcybahuwP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 5844 KB Line "aPacaoP---izjpfrpvhbP---------...------silP---zuknicjtukmwmlddzP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 14548 KB Line "aPadmeP---ejuixzggakP---------...----vP-wshP---gPkwzakqubhstcdqP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 62 ms 36040 KB Line "bPaPcbbeimbP-----sfP--xlpopwoc...------------fxdtggdqqcboxpukynP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 28136 KB Line "aPbPavpruP----edscfP------bnwl...vpiP--------jbfbP---jtearnhdjeP" doesn't correspond to pattern "[a-z\-P]{1}"
2 Halted 0 ms 0 KB -