# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
889085 | Macker | Type Printer (IOI08_printer) | C++17 | 127 ms | 60824 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{
node* par;
map<char, node*> m = {};
int d = 0;
int mxd = 0;
bool vis = 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({cur});
}
add(s, i + 1, cur->m[s[i]]);
}
int depthDfs(node* a){
if(a->m.size() == 1){
a->mxch = (*a->m.begin()).second;
a->d = depthDfs((*a->m.begin()).second) + 1;
}
else{
a->d = 0;
for (auto &b : a->m) {
int nd = depthDfs(b.second) + 1;
if(nd > a->mxd){
a->mxd = nd;
a->mxch = b.second;
}
}
}
return max(a->d, a->mxd - 1);
}
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({NULL});
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... |