Submission #227777

#	Time	Username	Problem	Language	Result	Execution time	Memory
227777		FieryPhoenix	Type Printer (IOI08_printer)	C++11	80 / 100	1100 ms	60460 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;
  for (int i=0;i<26;i++)
    if (trie[node].child[i]!=0)
      v.push_back({trie[trie[node].child[i]].max_depth,(char)(i+'a')});
  sort(v.begin(),v.end());
  for (int i=0;i<(int)v.size();i++){
    ans.push_back(v[i].second);
    dfs(trie[node].child[(int)(v[i].second-'a')]);
  }
  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();
  cout<<ans.size()<<endl;
  for (char c:ans)
    cout<<c<<endl;
  return 0;
}

• 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: 0 / 10
• Subtask 10: 0 / 10