Submission #1039123

#TimeUsernameProblemLanguageResultExecution timeMemory
1039123LudisseyType Printer (IOI08_printer)C++17
100 / 100
149 ms142792 KiB
#include <bits/stdc++.h> #define int long long #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() using namespace std; struct trie{ char c; trie* child[27]; vector<bool> visited; bool isEND=0; trie* parent; trie(trie* root, char _c){ for (int i = 0; i < 27; i++) child[i]=nullptr; this->visited.resize(27,0); isEND=false; c=_c; parent=root; } }; void add(trie* root, string s, int i){ if(i==sz(s)) { root->isEND=true; return; } if(root->child[s[i]-'a']==nullptr) root->child[s[i]-'a']=new trie(root,s[i]); add(root->child[s[i]-'a'],s,i+1); } trie* find_lowest_trie(trie* root, string s, int i){ if(i==sz(s)) return root; return find_lowest_trie(root->child[s[i]-'a'],s,i+1); } void remove_exist(trie* root ,int last){ if(root->c==' ') return; for (int i = 0; i < 27; i++) { if(root->child[i]!=nullptr&&i!=last) return; } int nl=root->c-'a'; root->parent->visited[nl]=true; remove_exist(root->parent,nl); } vector<char> ops; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<string> a(N); trie* root=new trie(nullptr,' '); for (int i = 0; i < N; i++) cin >> a[i]; for (int i = 0; i < N; i++) add(root,a[i],0); sort(all(a), [](string &_a, string &b){return sz(_a)<sz(b);}); trie* current=find_lowest_trie(root, a[N-1], 0); remove_exist(current,-1); while(true){ bool b=true; for (int i=0; i<27; i++) { if(current->child[i]==nullptr||current->visited[i]) continue; current->visited[i]=true; current=current->child[i]; ops.push_back('-'); b=false; } if(b) { if(current->c==' ') break; else { current->parent->visited[current->c-'a']=true; if(current->isEND) { ops.push_back('P'); current->isEND=false; } ops.push_back(current->c); current=current->parent; } } else continue; } cout << sz(ops) << "\n"; for (int i = sz(ops)-1; i >= 0; i--) { cout << ops[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...