# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
900655 | vanea | Type Printer (IOI08_printer) | C++14 | 66 ms | 40400 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;
using ll = long long;
const int mxN = 5e5+10;
int trie[mxN][26];
int cnt = 0;
bool stop[mxN];
string alpha = "abcdefghijklmnopqrstuvwxyz";
void insert(string s) {
int node = 0;
for(auto c : s) {
if(trie[node][c-'a'] == 0) trie[node][c-'a'] = ++cnt;
node = trie[node][c-'a'];
}
stop[node] = true;
}
vector<char> ans;
void dfs(int node) {
if(stop[node]) ans.push_back('P');
for(auto c : alpha) {
int k = trie[node][c-'a'];
if(k) {
ans.push_back(c);
dfs(k);
ans.push_back('-');
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++) {
string s;
cin >> s;
insert(s);
}
dfs(0);
int curr = 0, mx = 0, idx;
for(int i = 0; i < ans.size(); i++) {
if(ans[i] == '-') curr++;
else {
if(curr > mx) {
mx = curr;
idx = i;
}
curr = 0;
}
}
if(curr > mx) {
mx = curr;
idx = ans.size();
}
cout << ans.size() - mx << '\n';
for(int i = idx; i < ans.size(); i++) {
cout << ans[i] << '\n';
}
for(int i = 0; i < idx-mx; i++) {
cout << ans[i] << '\n';
}
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... |