Submission #589461

#TimeUsernameProblemLanguageResultExecution timeMemory
589461MamedovType Printer (IOI08_printer)C++17
100 / 100
154 ms120128 KiB
#pragma GCC optimize ("O3") #include <bits/stdc++.h> #define pii pair<int, int> #define piii pair<pii, int> #define vi vector<int> #define vvi vector<vi> #define vpii vector<pii> #define vvpii vector<vpii> #define f first #define s second #define oo 1000000001 #define eb emplace_back #define pb push_back #define mpr make_pair #define size(v) (int)v.size() #define ln '\n' #define ull unsigned long long #define ll long long #define all(v) v.begin(), v.end() using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); struct Trie { bool isEnd; int depth; vector<Trie*>link; Trie(int dep): isEnd(false), depth(dep), link(vector<Trie*>(26, nullptr)) {} void add(string &s) { Trie *node = this; int len = size(s); for (char c : s) { if (node->link[c - 'a']) { node = node->link[c - 'a']; node->depth = max(node->depth, len); } else { node = node->link[c - 'a'] = new Trie(len); } } node->isEnd = true; } string traverse(Trie *node) { string res = ""; if (node->isEnd) res += 'P'; int imaxDep = -1; for (int i = 0; i < 26; ++i) { if (node->link[i] && (imaxDep == -1 || node->link[i]->depth > node->link[imaxDep]->depth)) { imaxDep = i; } } if (imaxDep != -1) { for (int i = 0; i < 26; ++i) { if (i != imaxDep && node->link[i]) { res += ('a' + i); res += traverse(node->link[i]); res += '-'; } } res += ('a' + imaxDep); res += traverse(node->link[imaxDep]); res += '-'; } return res; } }; void solve() { int n; cin >> n; string s; Trie *root = new Trie(0); for (int i = 0; i < n; ++i) { cin >> s; root->add(s); } string res = root->traverse(root); while (res.back() == '-') res.pop_back(); cout << size(res) << ln; for (char c : res) { cout << c << ln; } } int main() { ios_base::sync_with_stdio(false); solve(); 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...