Submission #989452

#	Time	Username	Problem	Language	Result	Execution time	Memory
989452		huutuan	Type Printer (IOI08_printer)	C++14	100 / 100	97 ms	61240 KiB

printer

#include<bits/stdc++.h>

using namespace std;

struct Node{
   int cnt, end;
   int nxt[26];
   Node (){
      cnt=0; end=0;
      memset(nxt, -1, sizeof nxt);
   }
};

struct Trie{
   vector<Node> t;
   Trie (){
      t.emplace_back();
   }
   void add_string(const string &s, int x){
      int id=0;
      for (char cc:s){
         t[id].cnt+=x;
         int c=cc-'a';
         if (t[id].nxt[c]==-1){
            t[id].nxt[c]=t.size();
            t.emplace_back();
         }
         id=t[id].nxt[c];
      }
      t[id].cnt+=x;
      ++t[id].end;
   }
   void dfs(int id, vector<char> &ans){
      for (int i=0; i<(int)t[id].end; ++i) ans.push_back('P');
      for (int c=0; c<26; ++c) if (t[id].nxt[c]!=-1 && !t[t[id].nxt[c]].cnt){
         ans.push_back('a'+c);
         dfs(t[id].nxt[c], ans);
         ans.push_back('-');
      }
      for (int c=0; c<26; ++c) if (t[id].nxt[c]!=-1 && t[t[id].nxt[c]].cnt){
         ans.push_back('a'+c);
         dfs(t[id].nxt[c], ans);
      }
   }
} trie;

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int n;
   cin >> n;
   vector<string> v(n);
   for (auto &i:v) cin >> i;
   int id=max_element(v.begin(), v.end(), [&](string s, string t){ return s.size()<t.size(); })-v.begin();
   v.push_back(v[id]);
   v.erase(v.begin()+id);
   for (int i=0; i<n-1; ++i) trie.add_string(v[i], 0);
   trie.add_string(v.back(), 1);
   vector<char> ans;
   trie.dfs(0, ans);
   cout << ans.size() << '\n';
   for (char c:ans) cout << c << '\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