# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
797942 | 2023-07-30T07:36:47 Z | acatmeowmeow | Type Printer (IOI08_printer) | C++11 | 67 ms | 38936 KB |
#include <bits/stdc++.h> using namespace std; #define int long long struct trie { bool mark; int height = 1; trie *next[26]; void extend(int index) { if (!next[index]) next[index] = new trie(); } void add(string&s, int index) { if (s.size() - 1 == index) mark = true; else { char nextChar = s[index + 1]; extend(nextChar - 'a'); next[nextChar - 'a']->add(s, index + 1); } } void query(vector<char>&ans) { if (mark) ans.push_back('P'); for (int i = 0; i < 26; i++) { if (!next[i]) continue; ans.push_back(i + 'a'); next[i]->query(ans); ans.push_back('-'); } } void dfs() { for (int i = 0; i < 26; i++) { if (!next[i]) continue; next[i]->dfs(); height = max(height, next[i]->height + 1); } } }; const int N = 25000; int n; trie *root[26]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; i++) { string s; cin >> s; if (!root[s[0] - 'a']) root[s[0] - 'a'] = new trie(); root[s[0] - 'a']->add(s, 0); } vector<pair<int, int>> arr; for (int i = 0; i < 26; i++){ if (!root[i]) continue; root[i]->dfs(); arr.push_back({root[i]->height, i}); } sort(arr.begin(), arr.end()); vector<char> ans; for (auto&v : arr) { int index = v.second; ans.push_back(index + 'a'); root[index]->query(ans); ans.push_back('-'); } while (ans.size() && ans.back() == '-') ans.pop_back(); cout << ans.size() << '\n'; for (auto&v : ans) cout << v << '\n'; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 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 | Incorrect | 0 ms | 212 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 3 ms | 1876 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 6356 KB | Output is correct |
2 | Incorrect | 18 ms | 13352 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 20 ms | 15612 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 67 ms | 38936 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 46 ms | 30404 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |