oj.uz

Submission #74728

# Submission time Handle Problem Language Result Execution time Memory
74728 2018-09-07T03:10:59 Z goodbaton Type Printer (IOI08_printer) C++14
100 / 100
 159 ms 63772 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cstring>

using namespace std;
typedef long long ll;

#define SIZE 25010

struct NODE{
  int child[26];
  int max;
  bool fin;

  NODE(){
    for(int i=0;i<26;i++) child[i] = -1;
    max = 0;
    fin = false;
  }
};

NODE node[SIZE*21];
int node_size = 1;

char ans[SIZE*42];
int ans_size = 0;

int add(char *s,int now=0,int depth=0){

  if(s[depth]=='\0'){
    node[now].max = max(node[now].max,depth);
    node[now].fin = true;
    return node[now].max;
  }
  
  int next_c = s[depth]-'a';
  
  if(node[now].child[next_c]==-1){
    node[now].child[next_c] = node_size;
    node_size++;
  }

  node[now].max = max(node[now].max, add(s,node[now].child[next_c],depth+1) );

  return node[now].max;
}

bool fin = false;
int counter = 0;

void solve(int now=0){

  if(node[now].fin) ans[ans_size++] = 'P';
  counter++;
  
  for(int i=0;i<26;i++){
    if(node[now].child[i]==-1) continue;

    int to = node[now].child[i];
    
    if(node[now].max != node[to].max){
      ans[ans_size++] = 'a'+i;
      solve(to);
    }
  }

  for(int i=0;i<26;i++){
    if(node[now].child[i]==-1) continue;

    int to = node[now].child[i];
    
    if(node[now].max == node[to].max){
      ans[ans_size++] = 'a'+i;
      solve(to);
    }
  }

  if(counter!=node_size) ans[ans_size++] = '-';
}

int main(){
  int n;
  char word[25];

  scanf("%d",&n);

  for(int i=0;i<n;i++){
    scanf("%s",word);
    add(word);
  }
  
  solve();

  printf("%d\n",ans_size);

  for(int i=0;i<ans_size;i++){
    printf("%c\n",ans[i]);
  }
  
  return 0;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
printer.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",word);
     ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 57852 KB Output is correct
2 Correct 46 ms 58000 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 58024 KB Output is correct
2 Correct 52 ms 58024 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 58024 KB Output is correct
2 Correct 48 ms 58076 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 58076 KB Output is correct
2 Correct 52 ms 58076 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 58320 KB Output is correct
2 Correct 51 ms 58348 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 58428 KB Output is correct
2 Correct 63 ms 58696 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 58940 KB Output is correct
2 Correct 53 ms 58940 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 59708 KB Output is correct
2 Correct 159 ms 61728 KB Output is correct
3 Correct 108 ms 61728 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 61728 KB Output is correct
2 Correct 154 ms 63036 KB Output is correct
3 Correct 104 ms 63036 KB Output is correct
4 Correct 144 ms 63772 KB Output is correct