# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
114527 | popovicirobert | Type Printer (IOI08_printer) | C++14 | 183 ms | 99296 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |