#include <bits/stdc++.h>
using namespace std;
#define MAXN 25005
vector<pair<int, char>> adj[20*MAXN];
int dp1[MAXN*20], dp2[MAXN*20];
int ans[MAXN*20];
string words[MAXN];
int n;
int cur = 0;
pair<int, char> nodes[MAXN*20];
string ts;
int cnt = 0;
void addWord(int v, int p, int index){
if(index == ts.length()){
adj[v].push_back({++cur, 'P'});
adj[cur].push_back(nodes[v]);
nodes[cur] = {cur, 'P'};
return;
}
bool flag = false;
for(auto u : adj[v]){
if(p == u.first) continue;
if(u.second == ts[index]){
flag = true;
addWord(u.first, v, index+1);
}
}
if(!flag){
adj[v].push_back({++cur, ts[index]});
adj[cur].push_back(nodes[v]);
nodes[cur] = {cur, ts[index]};
addWord(cur, v, index+1);
}
}
void calc(int v, int p){
dp1[v] = dp2[v] = 0;
ans[v] = v;
vector<int> dd2;
for(auto u : adj[v]){
if(u.first == p){
dd2.push_back(1000000009);
continue;
}
calc(u.first, v);
dp1[v] += dp1[u.first]+2;
dd2.push_back(dp2[u.first]-dp1[u.first]);
}
dp2[v] = dp1[v];
int mi = 1000000000, mindex = -1;
for(int i = 0; i<dd2.size(); i++){
if(dd2[i] < mi){
mi = dd2[i];
mindex = adj[v][i].first;
}
}
if(mi == 1000000000) return;
ans[v] = mindex;
dp2[v] = dp2[v]+mi-1;
}
void getAns(int v, int p){
for(auto u : adj[v]){
if(u.first == p || u.first == ans[v]) continue;
cout << u.second << endl;
getAns(u.first, v);
if(cnt != n) cout << '-' << endl;
}
if(ans[v] != v){
for(auto u : adj[v]){
if(u.first == ans[v]){
cout << u.second << endl;
getAns(u.first, v);
if(cnt != n) cout << '-' << endl;
break;
}
}
}
else cnt++;
}
int main(){
freopen("a.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
nodes[0] = {0, '?'};
for(int i = 0; i<n; i++){
cin >> words[i];
ts = words[i];
addWord(0, -1, 0);
}
calc(0, -1);
// for(int i = 0; i<=cur; i++){
// cout << i << " " << nodes[i].second << endl;
// for(auto u : adj[i]){
// cout << u.first << " ";
// }
// cout << endl;
// cout << endl;
// }
cout << dp2[0]-n+1 << endl;
getAns(0, -1);
}
Compilation message
printer.cpp: In function 'void addWord(int, int, int)':
printer.cpp:16:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | if(index == ts.length()){
| ~~~~~~^~~~~~~~~~~~~~
printer.cpp: In function 'void calc(int, int)':
printer.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i = 0; i<dd2.size(); i++){
| ~^~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:85:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
85 | freopen("a.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12928 KB |
Line "" doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12928 KB |
Line "" doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12928 KB |
Line "" doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12928 KB |
Line "" doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12928 KB |
Line "" doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12928 KB |
Line "" doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
12928 KB |
Line "" doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12928 KB |
Line "" doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12928 KB |
Line "" doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
12928 KB |
Line "" doesn't correspond to pattern "[a-z\-P]{1}" |
| 2 |
Halted |
0 ms |
0 KB |
- |
