Submission #131889

#	Time	Username	Problem	Language	Result	Execution time	Memory
131889		dragonslayerit	Type Printer (IOI08_printer)	C++14	100 / 100	207 ms	51676 KiB

printer

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

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