oj.uz

Submission #605403

# Submission time Handle Problem Language Result Execution time Memory
605403 2022-07-25T17:10:48 Z oscarsierra12 Type Printer (IOI08_printer) C++14
100 / 100
 157 ms 52300 KB 
#include <bits/stdc++.h>
using namespace std;

#define endl   "\n";

const int N=25010;
int arr[20*N][26];
int cnt = 1;
int dp[20*N][2];
int terminal[20*N];

void add(string s){
  int node = 1;
  for (int i = 0; i < s.size(); ++i){
    if (arr[node][s[i]-'a'] == 0){
      cnt++;
      arr[node][s[i]-'a'] = cnt;
    } 
    node = arr[node][s[i]-'a'];
    if (i == s.size()-1){
      terminal[node] = 1;
    }
  }
}

int go(int node, int flag){
  int &rf = dp[node][flag];
  if (rf != -1) {
    return rf;
  }
  int sum = flag;
  for(int i = 0; i < 26; ++i){
    if(arr[node][i]!=0)
      sum+=1+go(arr[node][i],1);
  }
  if (flag) return rf = sum;
  if (sum == 0) return rf=0;
  rf=40*N;
  for(int i = 0; i < 26; ++i){
    if(arr[node][i]!=0){
      int nsum = sum - go(arr[node][i],1) + go(arr[node][i],0);
      rf = min(rf, nsum);
    }
  }
  return rf;
}

void build (int node, int flag) {
  int &rf = dp[node][flag];
  if(terminal[node])cout<<"P"<<endl;
  if(flag==1){
    for(int i = 0; i < 26; ++i){
      if(arr[node][i]!=0) {
        cout << (char)(i+'a') << endl;
        build(arr[node][i],1);
      }
    }  
    cout<<"-"<<endl;
  }
  else{
      int sum = 0,esp=0;
      for(int i = 0; i < 26; ++i){
        if(arr[node][i]!=0)
          sum+=1+go(arr[node][i],1);
      }
      if(sum==0)return;
      for(int i = 0; i < 26; ++i){
        if(arr[node][i]!=0){
          int nsum = sum - go(arr[node][i],1) + go(arr[node][i],0);
          if(rf==nsum){
             esp = i; 
          }
        }
      }
        for(int i = 0; i < 26; ++i){
          if(arr[node][i]!=0&&i!=esp) {
            
            cout << (char)(i+'a') << endl;
            build(arr[node][i],1);
          }
        } 
        assert(arr[node][esp]>0);
        cout << char(esp+'a')<<endl;
        build(arr[node][esp],0);
      }    
  }

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int n; cin >> n;
  for (int i = 0; i < n; ++i){
    string word;
    cin >> word;
    add(word);
  }
  memset(dp,-1,sizeof dp);
  cout<<go(1,0)+n<<endl;
  build(1,0);
}

Compilation message

printer.cpp: In function 'void add(std::string)':
printer.cpp:14:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for (int i = 0; i < s.size(); ++i){
      |                   ~~^~~~~~~~~~
printer.cpp:20:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     if (i == s.size()-1){
      |         ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4216 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 4 ms 4608 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4948 KB Output is correct
2 Correct 6 ms 5204 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6868 KB Output is correct
2 Correct 29 ms 10036 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11112 KB Output is correct
2 Correct 9 ms 5588 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 21756 KB Output is correct
2 Correct 128 ms 44520 KB Output is correct
3 Correct 88 ms 24876 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 17912 KB Output is correct
2 Correct 157 ms 52300 KB Output is correct
3 Correct 84 ms 28172 KB Output is correct
4 Correct 143 ms 50064 KB Output is correct