Submission #518266

#	Time	Username	Problem	Language	Result	Execution time	Memory
518266		plains4	Type Printer (IOI08_printer)	C++14	100 / 100	179 ms	96968 KiB

printer

#include<bits/stdc++.h>

using namespace std;

const int CHAR_COUNT = 26;

struct node {
  bool cnt_leaf;
  short max_depth;
  
  unordered_map<short, node*> nx;
  
  node() {
    cnt_leaf = max_depth = 0;
  }
};

string ans;
node *root = new node();

node* insert(node *cur, string &s, int dep) {
  if(s.length() == dep){
    cur->cnt_leaf = true;
    cur->max_depth = max(cur->max_depth, (short)dep);
    return cur;
  }
  
  int ch = s[dep] - 'a';
  if(cur->nx.count(ch) == 0)cur->nx[ch] = new node();
  cur->nx[ch] = insert(cur->nx[ch], s, dep + 1);
  
  cur->max_depth = max(cur->max_depth, cur->nx[ch]->max_depth);
  // cout << "Done Traverse from " << s[dep] << " -> " << (int)s[dep] << " " << cur->max_depth << endl;
  return cur;
}

void print(node *cur){
  if(cur == NULL)return;
  int last = -1;
  short maxi = -1;
  for(auto x: cur->nx) {
    // cout << "exist to " << (char)(i) << endl;
    if(maxi < x.second->max_depth){
      maxi = x.second->max_depth;
      last = x.first;
    }
  }
  
  if(cur->cnt_leaf > 0)ans += "P";
  
  for(auto x: cur->nx){
    if(x.first == last)continue;
    
    // cout << "Print Traverse to " << (char)(i) << " -> " << i << endl;
    ans += (char)(x.first + 'a');
    print(x.second);
    ans += "-";
  }
  
  if(last != -1){
    ans += (char)(last + 'a');
    print(cur->nx[last]);
    ans += "-";
  }
}

int main(){
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  int n; cin >> n;
  while(n--){
    string s; cin >> s;
    root = insert(root, s, 0);
  }
  // cout << sizeof(root->nx) + sizeof(root->cnt_leaf) + sizeof(root->max_depth) << endl;
  // cout << "Start Root" << endl;
  print(root);
  while(ans.size() > 0 && ans.back() == '-') ans.pop_back();
  cout << ans.size() << "\n";
  for(int i = 0; i < ans.size(); i++){
    cout << ans[i] << "\n";
  }
}

Compilation message (stderr)

printer.cpp: In constructor 'node::node()':
printer.cpp:14:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   14 |     cnt_leaf = max_depth = 0;
      |                ~~~~~~~~~~^~~
printer.cpp: In function 'node* insert(node*, std::string&, int)':
printer.cpp:22:17: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |   if(s.length() == dep){
      |      ~~~~~~~~~~~^~~~~~
printer.cpp: In function 'int main()':
printer.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i = 0; i < ans.size(); i++){
      |                  ~~^~~~~~~~~~~~

• 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