oj.uz

Submission #131889

# Submission time Handle Problem Language Result Execution time Memory
131889 2019-07-17T21:42:13 Z dragonslayerit Type Printer (IOI08_printer) C++14
100 / 100
 207 ms 51676 KB 
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>

struct Node{
  int chd[26];
  int has;
  int depth;
}nodes[500005];
int nodes_cnt=1;

char str[64];
int longest=0;

int getchild(int node,int c){
  int& ret=nodes[node].chd[c];
  if(!ret){
    ret=nodes_cnt++;
  }
  return ret;
}

void add(){
  int curr=0;
  for(int i=0;str[i];i++){
    curr=getchild(curr,str[i]-'a');
  }
  nodes[curr].has=true;
}

std::string ans;

void dfs(int node){
  for(int c=0;c<26;c++){
    int child=nodes[node].chd[c];
    if(child){
      dfs(child);
      nodes[node].depth=std::max(nodes[node].depth,nodes[child].depth+1);
    }
  }
}

void output(int node){
  if(nodes[node].has) ans+='P';
  int deep=-1;
  for(int c=0;c<26;c++){
    if(nodes[node].chd[c]){
      if(deep==-1||nodes[nodes[node].chd[c]].depth>nodes[nodes[node].chd[deep]].depth){
	deep=c;
      }
    }
  }
  for(int c=0;c<26;c++){
    if(nodes[node].chd[c]&&c!=deep){
      ans+='a'+c;
      output(nodes[node].chd[c]);
      ans+='-';
    }
  }
  for(int c=0;c<26;c++){
    if(nodes[node].chd[c]&&c==deep){
      ans+='a'+c;
      output(nodes[node].chd[c]);
      ans+='-';
    }
  }
}

int main(){
  int N;
  scanf("%d",&N);
  for(int i=0;i<N;i++){
    scanf("%s",str);
    add();
    longest=std::max<int>(longest,strlen(str));
  }
  int len=nodes_cnt*2-2-longest+N;
  dfs(0);
  output(0);
  ans.resize(len);
  printf("%d\n",len);
  for(char c:ans){
    printf("%c\n",c);
  }
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3320 KB Output is correct
2 Correct 26 ms 6776 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 7816 KB Output is correct
2 Correct 12 ms 2040 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 19220 KB Output is correct
2 Correct 177 ms 43568 KB Output is correct
3 Correct 91 ms 22676 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 15120 KB Output is correct
2 Correct 207 ms 51676 KB Output is correct
3 Correct 105 ms 25748 KB Output is correct
4 Correct 187 ms 48788 KB Output is correct