Submission #605402

#	Time	Username	Problem	Language	Result	Execution time	Memory
605402		oscarsierra12	Type Printer (IOI08_printer)	C++14	90 / 100	1084 ms	52224 KiB

printer

#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() {
  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 (stderr)

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 / 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: 0 / 10