| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 872450 | ObadaKh | Type Printer (IOI08_printer) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp> using namespace std;using namespace __gnu_pbds;/*-------------------------*/#define ll long long#define ld long double#define all(v) v.begin(),v.end()#define allr(v) v.rbegin(),v.rend()#define Dracarys ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);template<typename T> using indexed_multiset = tree<T, null_type, greater_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;typedef pair<ll, int> pi;const int N = 2e5 + 10;const int infi = 1e9 + 10;const ll infl = 1e18 + 10;const int MOD = 1e9 + 7;const ld eps = 1e-9; string ScanString() { char ch[100000]; scanf("%s", ch); return ch;} vector<char> Ans;const int CHAR = 26; struct TrieNode { TrieNode *child[CHAR]; int Cnt, End, mxval; TrieNode() { memset(child, 0, sizeof child); Cnt = End = mxval = 0; } void add(int i, string &s) { int cur = s[i] - 'a'; if (child[cur] == 0) child[cur] = new TrieNode(); child[cur]->Cnt++; if (i == s.size() - 1) { child[cur]->End++; mxval = s.size(); return; } child[cur]->add(i + 1, s); } void add(string &s) { add(0, s); } void erase(int i, string &s) { int cur = s[i] - 'a'; child[cur]->Cnt--; if (i == s.size() - 1) { child[cur]->End--; return; } child[cur]->erase(i + 1, s); if (!child[cur]->Cnt) { delete child[cur]; child[cur] = 0; } } void erase(string &s) { if (!find(s))return; erase(0, s); } bool find(int i, string &s) { int cur = s[i] - 'a'; if (child[cur] == 0)return 0; if (i == s.size() - 1) { return child[cur]->End > 0; } return child[cur]->find(i + 1, s); } bool find(string &s) { return find(0, s); } int CntPrefix(int i, string &s) { int cur = s[i] - 'a'; if (child[cur] == 0)return 0; if (i == s.size() - 1) { return child[cur]->Cnt; } return child[cur]->CntPrefix(i + 1, s); } int CntPrefix(string &s) { return CntPrefix(0, s); } void DfsMax() { for (int i = 0; i < 26; i++) { if (child[i]) child[i]->DfsMax(), mxval = max(mxval, child[i]->mxval); } } void Dfs() { set<pair<int, int>> st; for (int i = 0; i < 26; i++) if (child[i]) st.insert({child[i]->mxval, i}); for (auto &it: st) { Ans.push_back(char('a' + it.second)); if (child[it.second]->End)Ans.push_back('P'); child[it.second]->Dfs(); Ans.push_back('-'); } } void clear() { for (int i = 0; i < CHAR; i++) if (child[i]) child[i]->clear(), delete child[i], child[i] = 0; }}; void RunTime(int Tc) { int n; cin >> n; TrieNode *Root = new TrieNode(); for (int i = 0; i < n; i++) { string s; cin >> s; Root->add(s); } Root->DfsMax(); Root->Dfs(); while (Ans.back() == '-')Ans.pop_back(); cout << Ans.size() << endl; for (auto &it: Ans)cout << it << endl;} int main() { Dracarys int T = 1; //cin >> T; for (int Tc = 1; Tc <= T; Tc++) { RunTime(Tc); } return 0;}