# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
659636 | 2022-11-18T20:30:03 Z | pakapu | Type Printer (IOI08_printer) | C++17 | 120 ms | 101568 KB |
#include <bits/stdc++.h> using namespace std; struct node { node* c[26]; bool end = false; bool marked = false; node() { for(int i = 0; i < 26; i++) { c[i] = nullptr; } } }; vector<char> result; struct trie { node* head; trie() { head = new node; head -> marked = true; } void add(string s, bool m) { node* curr = head; for(int i = 0; i < s.size(); i++) { if(curr -> c[s[i] - 'a'] == nullptr) { curr -> c[s[i] - 'a'] = new node; } curr = curr -> c[s[i] - 'a']; curr -> marked = m; } curr -> end = true; } void out() { out(head, nullptr); } void out(node* v, node* prev) { if(v -> end) { result.push_back('P'); } int mi = -1; for(int i = 0; i < 26; i++) { if(v -> c[i] != nullptr) { if(v -> c[i] -> marked) { mi = i; continue; } result.push_back((char)(i + 'a')); out(v -> c[i], v); } } if(mi != -1) { result.push_back((char)(mi + 'a')); out(v -> c[mi], v); } if(!v -> marked) { result.push_back('-'); } } }; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector<string> a(n); string mx = ""; for(int i = 0; i < n; i++) { cin >> a[i]; if(a[i].size() > mx.size()) { mx = a[i]; } } trie t; for(auto c : a) { t.add(c, false); } t.add(mx, true); t.out(); assert(result.back() == 'P'); cout << result.size() << '\n'; for(auto c : result) { cout << c << '\n'; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 224 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 320 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 2 ms | 1108 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 1876 KB | Output is correct |
2 | Correct | 3 ms | 2244 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 5972 KB | Output is correct |
2 | Correct | 16 ms | 12796 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 14976 KB | Output is correct |
2 | Correct | 11 ms | 3924 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 48 ms | 37188 KB | Output is correct |
2 | Correct | 107 ms | 85300 KB | Output is correct |
3 | Correct | 67 ms | 44932 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 29176 KB | Output is correct |
2 | Correct | 120 ms | 101568 KB | Output is correct |
3 | Correct | 67 ms | 50912 KB | Output is correct |
4 | Correct | 100 ms | 95904 KB | Output is correct |