Submission #114527

#TimeUsernameProblemLanguageResultExecution timeMemory
114527popovicirobertType Printer (IOI08_printer)C++14
100 / 100
183 ms99296 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long // 217 // 44 using namespace std; struct Trie { Trie *son[26]; int mx, cnt; Trie() { memset(son, 0, sizeof(son)); mx = cnt = 0; } }; Trie *root = new Trie; void add(Trie *nod, string &str, int p) { if(p < str.size()) { char ch = str[p] - 'a'; if(nod -> son[ch] == NULL) { nod -> son[ch] = new Trie; } add(nod -> son[ch], str, p + 1); nod -> mx = max(nod -> mx, nod -> son[ch] -> mx + 1); } else { nod -> cnt++; } } string sol; void dfs(Trie *nod) { int id = -1; for(int ch = 0; ch < 26; ch++) { if(nod -> son[ch] == NULL) { continue; } if(nod -> son[ch] -> mx + 1 == nod -> mx) { id = ch; } } while(nod -> cnt > 0) { sol.push_back('P'); nod -> cnt--; } for(int ch = 0; ch < 26; ch++) { if(id != ch && nod -> son[ch] != NULL) { sol.push_back(ch + 'a'); dfs(nod -> son[ch]); sol.push_back('-'); } } if(id > -1) { sol.push_back(id + 'a'); dfs(nod -> son[id]); sol.push_back('-'); } } int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, n; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n; string str; for(i = 0; i < n; i++) { cin >> str; add(root, str, 0); } dfs(root); while(sol.back() == '-') { sol.pop_back(); } cout << sol.size() << "\n"; for(auto it : sol) { cout << it << "\n"; } //cin.close(); //cout.close(); return 0; }

Compilation message (stderr)

printer.cpp: In function 'void add(Trie*, std::__cxx11::string&, int)':
printer.cpp:23:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(p < str.size()) {
        ~~^~~~~~~~~~~~
printer.cpp:25:25: warning: array subscript has type 'char' [-Wchar-subscripts]
         if(nod -> son[ch] == NULL) {
                         ^
printer.cpp:26:26: warning: array subscript has type 'char' [-Wchar-subscripts]
             nod -> son[ch] = new Trie;
                          ^
printer.cpp:28:26: warning: array subscript has type 'char' [-Wchar-subscripts]
         add(nod -> son[ch], str, p + 1);
                          ^
printer.cpp:29:49: warning: array subscript has type 'char' [-Wchar-subscripts]
         nod -> mx = max(nod -> mx, nod -> son[ch] -> mx + 1);
                                                 ^
#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...