# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
673786 | chanhchuong123 | Type Printer (IOI08_printer) | C++14 | 56 ms | 34916 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;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int MAX = 500000;
int n;
string s;
int dp[MAX];
int numNode;
char c[MAX];
int nxt[MAX][26];
vector<int> adj[MAX];
void add(string s) {
int p = 0;
for (int i = 0; i < s.size(); ++i) {
int LOVE = s[i] - 'a';
if (nxt[p][LOVE] == 0) {
c[numNode + 1] = s[i];
nxt[p][LOVE] = ++numNode;
adj[p].push_back(numNode);
}
p = nxt[p][LOVE];
}
}
void dfs(int u) {
for (int v: adj[u]) {
dfs(v);
maxi(dp[u], dp[v] + 1);
}
}
string res;
void re_dfs(int u) {
if (adj[u].empty()) {
res += 'P';
res += '-';
return;
}
for (int v: adj[u]) {
res += c[v];
re_dfs(v);
}
res += '-';
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> s;
add(s);
}
dfs(0);
for (int i = 0; i <= numNode; ++i) {
sort(all(adj[i]), [&](int u, int v) {
return dp[u] < dp[v];
});
}
re_dfs(0); dp[0]++;
while (dp[0]--) res.pop_back();
cout << res.size() << '\n';
for (char &c: res)
cout << c << '\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... |