# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
889088 | Macker | Type Printer (IOI08_printer) | C++17 | 113 ms | 54476 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>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
struct node{
map<char, node*> m = {};
int d = 0;
int mxd = 0;
node* mxch = NULL;
bool end = 0;
};
void add(string s, int i, node* cur){
if(i == s.size()){
cur->end = true;
return;
}
if(cur->m.find(s[i]) == cur->m.end()){
cur->m[s[i]] = new node();
}
add(s, i + 1, cur->m[s[i]]);
}
void depthDfs(node* a){
if(a->m.size() == 1){
node* nx = (*a->m.begin()).second;
a->mxch = nx;
depthDfs((*a->m.begin()).second);
a->mxd = nx->mxd;
a->d = nx->d + 1;
}
else{
for (auto &b : a->m) {
depthDfs(b.second);
int nd = max(b.second->d + 1, b.second->mxd);
if(nd > a->mxd){
a->mxd = nd;
a->mxch = b.second;
}
}
}
}
vector<char> res;
void resDfs(node* a, bool first){
char c;
if(a->end) res.push_back('P');
for (auto &b : a->m) {
if(b.second == a->mxch && first){
c = b.first;
continue;
}
res.push_back(b.first);
resDfs(b.second, false);
res.push_back('-');
}
if(first && a->mxch){
res.push_back(c);
resDfs(a->mxch, true);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
node* root = new node();
for (int i = 0; i < n; i++) {
string s; cin >> s;
add(s, 0, root);
}
depthDfs(root);
resDfs(root, true);
cout << res.size() << endl;
for (auto &i : res)
cout << i <<"\n";
}
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... |