Submission #70425

#	Time	Username	Problem	Language	Result	Execution time	Memory
70425		doowey	Type Printer (IOI08_printer)	C++14	100 / 100	275 ms	100280 KiB

printer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double db;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO std::ios::sync_with_stdio(false);cin.tie(NULL);
#define TEST freopen("in.txt","r",stdin);
#define ones(a) __builtin_popcount(a);
#define pq priority_queue

struct Node{
  Node *nex[26];
  bool ends;
  int subt;
  Node(){
    for(int i = 0; i < 26;i ++ )
      nex[i] = NULL;
    ends = false;
    subt = 1;
  }
};

Node *Trie = new Node();

vector<char> oper;

int n;
int cnt;

void walk(Node *cur){
  for(int j = 0;j < 26;j ++ ){
    if(cur -> nex[j] != NULL){
      walk(cur -> nex[j]);
      cur -> subt = max(cur -> subt, cur -> nex[j] -> subt);
    }
  }
}

void dfs(Node *cur, bool is_root){
  if(cur -> ends){
    oper.push_back('P');
    cnt ++ ;
  }
  vector<pii> order;
  for(int j = 0;j < 26;j ++ ){
    if(cur -> nex[j] != NULL)
      order.push_back(mp(cur -> nex[j] -> subt, j));
  }
  sort(order.begin(), order.end());
  for(auto x : order){
    if(cur -> nex[x.se] != NULL){
      oper.push_back(char(x.se + 'a'));
      dfs(cur -> nex[x.se], false);
    }
  }
  if(!is_root and cnt != n){
    oper.push_back('-');
  }
}

int main(){
  fastIO;
  cin >> n;
  string a;
  for(int i = 0;i < n;i ++ ){
    cin >> a;
    Node *cur = Trie;
    for(char x : a){
      if(cur -> nex[x - 'a'] == NULL){
        cur -> nex[x - 'a'] = new Node();
      }
      cur = cur -> nex[x - 'a'];
    }
    cur -> subt = a.size();
    cur -> ends = true;
  }
  walk(Trie);
  dfs(Trie, true);
  cout << oper.size() << "\n";
  for(auto x : oper)
    cout << x << "\n";
  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: 10 / 10
• Subtask 10: 10 / 10