oj.uz

Submission #605400

# Submission time Handle Problem Language Result Execution time Memory
605400 2022-07-25T17:06:20 Z oscarsierra12 Type Printer (IOI08_printer) C++14
80 / 100
 1000 ms 52620 KB 
#include <bits/stdc++.h>
using namespace std;
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() {
  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:11:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |   for (int i = 0; i < s.size(); ++i){
      |                   ~~^~~~~~~~~~
printer.cpp:17:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     if (i == s.size()-1){
      |         ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4236 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 3 ms 4144 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 4144 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 4984 KB Output is correct
2 Correct 26 ms 5148 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6888 KB Output is correct
2 Correct 191 ms 10148 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 11184 KB Output is correct
2 Correct 60 ms 5776 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 21968 KB Output is correct
2 Execution timed out 1077 ms 44960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 18172 KB Output is correct
2 Execution timed out 1058 ms 52620 KB Time limit exceeded
3 Halted 0 ms 0 KB -