oj.uz

Submission #518266

# Submission time Handle Problem Language Result Execution time Memory
518266 2022-01-23T09:30:38 Z plains4 Type Printer (IOI08_printer) C++14
100 / 100
 179 ms 96968 KB 
#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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5608 KB Output is correct
2 Correct 27 ms 11852 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 13924 KB Output is correct
2 Correct 12 ms 3280 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 34816 KB Output is correct
2 Correct 137 ms 81400 KB Output is correct
3 Correct 104 ms 40880 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 26292 KB Output is correct
2 Correct 179 ms 96968 KB Output is correct
3 Correct 93 ms 46356 KB Output is correct
4 Correct 167 ms 91308 KB Output is correct