Submission #1297037

#TimeUsernameProblemLanguageResultExecution timeMemory
1297037harryleeeType Printer (IOI08_printer)C++20
100 / 100
94 ms58012 KiB
#include<bits/stdc++.h> using namespace std; const int maxn = 25000; int n; vector<char> res; struct TRIE{ struct NODE{ int nxt[26], cnt, len; inline NODE(){ fill(nxt, nxt + 26, -1); cnt = len = 0; } }; vector<NODE> node; inline TRIE(){ node.push_back(NODE()); } inline void insert(const string& s){ int pos = 0; for (int i = 0; i < s.size(); ++i){ int c = s[i] - 'a'; if (node[pos].nxt[c] == -1){ node[pos].nxt[c] = node.size(); node.push_back(NODE()); } pos = node[pos].nxt[c]; node[pos].len = max(node[pos].len, (int)s.size()); } node[pos].cnt++; return; } inline void DFS(int pos){ if (node[pos].cnt > 0) res.push_back('P'); vector<pair<int, int>> v; for (int i = 0; i < 26; ++i) if (node[pos].nxt[i] != -1){ v.push_back({node[node[pos].nxt[i]].len, i}); } sort(v.begin(), v.end()); for (pair<int, int> x : v){ res.push_back((char)('a' + x.second)); DFS(node[pos].nxt[x.second]); } res.push_back('-'); return; } } trie; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i < n; ++i){ string s; cin >> s; trie.insert(s); } trie.DFS(0); while(res.back() == '-') res.pop_back(); cout << res.size() << '\n'; for (char x : res) cout << x << '\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...