# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
858953 | ntkphong | Type Printer (IOI08_printer) | C++14 | 38 ms | 37484 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;
const int mxN = 100010;
struct node {
int w_count;
int child[26];
};
int n;
vector<string> s;
vector<node> tree;
vector<int> mark(mxN * 20);
vector<char> answer;
int id_max;
int cnt = 0;
void new_node() {
node x;
x.w_count = 0;
for(int i = 0; i < 26; i ++) x.child[i] = -1;
tree.push_back(x);
}
void init() {
new_node();
}
void add(string s, int type) {
int idx = 0;
for(int i = 0; i < s.size(); i ++) {
int w = s[i] - 'a';
if(tree[idx].child[w] == -1) {
new_node();
tree[idx].child[w] = tree.size() - 1;
}
idx = tree[idx].child[w];
mark[idx] = type;
}
tree[idx].w_count ++ ;
}
void _dfs(int u) {
for(int i = 1; i <= tree[u].w_count; i ++) {
answer.push_back('P');
cnt ++ ;
}
if(cnt == n) {
cout << answer.size() << "\n";
for(auto c : answer) cout << c;
exit(0);
}
for(int i = 0; i < 26; i ++) {
int v = tree[u].child[i];
if(v == -1) continue ;
if(!mark[v]) {
answer.push_back((char)(i + 'a'));
_dfs(v);
answer.push_back('-');
}
}
for(int i = 0; i < 26; i ++) {
int v = tree[u].child[i];
if(v == -1) continue ;
if(mark[v]) {
answer.push_back((char)(i + 'a'));
_dfs(v);
answer.push_back('-');
}
}
}
int main() {
#define taskname ""
if(fopen(taskname".inp", "r")) {
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
cin.tie(0)->sync_with_stdio(0);
cin >> n;
s.resize(n + 1);
init();
for(int i = 1; i <= n; i ++) {
cin >> s[i];
if(s[i].size() > s[id_max].size()) {
id_max = i;
}
}
for(int i = 1; i <= n; i ++) {
if(i == id_max) continue ;
add(s[i], 0);
}
add(s[id_max], 1);
_dfs(0);
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... |