Submission #227778

#	Time	Username	Problem	Language	Result	Execution time	Memory
227778		FieryPhoenix	Type Printer (IOI08_printer)	C++11	100 / 100	279 ms	60456 KiB

printer

#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

struct Node{
  int child[26];
  bool end;
  int depth,max_depth;
  Node(){
    for (int i=0;i<26;i++)
      child[i]=0;
    end=false;
    depth=0;
    max_depth=0;
  }
};

vector<Node>trie;

int get_child(int node, int target){
  if (trie[node].child[target]==0){
    trie[node].child[target]=trie.size();
    trie.emplace_back();
  }
  return trie[node].child[target];
}

void add(string s){
  int cur=0;
  vector<int>v;
  for (char c:s){
    int nex=get_child(cur,(int)(c-'a'));
    trie[nex].depth=trie[cur].depth+1;
    trie[nex].max_depth=max(trie[nex].depth,trie[nex].max_depth);
    v.push_back(nex);
    cur=nex;
  }
  trie[cur].end=true;
  cur=0;
  reverse(v.begin(),v.end());
  for (int i=1;i<(int)v.size();i++)
    trie[v[i]].max_depth=max(trie[v[i]].max_depth,trie[v[i-1]].max_depth);
  cout<<endl;
}

vector<char>ans;

void dfs(int node){
  if (trie[node].end)
    ans.push_back('P');
  vector<pair<int,char>>v;
  int mx=-1,ind=-1;
  for (int i=0;i<26;i++)
    if (trie[node].child[i]!=0 && trie[trie[node].child[i]].max_depth>mx){
      mx=trie[trie[node].child[i]].max_depth;
      ind=i;
    }
  for (int i=0;i<26;i++){
    if (trie[node].child[i]!=0 && ind!=i){
      ans.push_back((char)(i+'a'));
      dfs(trie[node].child[i]);
    }
  }
  if (ind!=-1){
    ans.push_back((char)(ind+'a'));
    dfs(trie[node].child[ind]);
  }
  ans.push_back('-');
}

int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  int N;
  cin>>N;
  trie.emplace_back();
  for (int i=0;i<N;i++){
    string S;
    cin>>S;
    add(S);
  }
  dfs(0);
  while (ans.back()=='-') ans.pop_back();
  printf("%d\n",ans.size());
  for (char c:ans)
    printf("%c\n",c);
  return 0;
}

Compilation message (stderr)

printer.cpp: In function 'int main()':
printer.cpp:91:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<char>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d\n",ans.size());
                 ~~~~~~~~~~^

• 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