oj.uz

답안 #605402

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
605402 2022-07-25T17:09:19 Z oscarsierra12 Type Printer (IOI08_printer) C++14
90 / 100
 1000 ms 52224 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() {
  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: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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 3 ms 4180 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4180 KB Output is correct
2 Correct 2 ms 4180 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 11 ms 4564 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 4980 KB Output is correct
2 Correct 26 ms 5168 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 7040 KB Output is correct
2 Correct 163 ms 10088 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 11116 KB Output is correct
2 Correct 57 ms 5624 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 430 ms 21772 KB Output is correct
2 Correct 952 ms 44584 KB Output is correct
3 Correct 553 ms 25464 KB Output is correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 333 ms 17836 KB Output is correct
2 Execution timed out 1084 ms 52224 KB Time limit exceeded
3 Halted 0 ms 0 KB -