#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define f first
#define s second
#define ii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define vvii vector<vector<ii>>
#define pb push_back
#define vpi vector<ii>
#define forcin for(int i = 0; i<n; ++i) cin>>v[i];
#define pq priority_queue<ii>
#define mp make_pair
#define ld long double
#define vc vector<char>
#define vvc vector<vc>
#define vb vector<bool>
#define vvb vector<vb>
#define all(a) (a).begin(),(a).end()
#define For(i, n, x) for (int i = x; i < n; i++)
#define rsz(a,x) assign(a,x)
#define endl "\n"
int n;
struct Node{
unordered_map<char,Node*> son;
bool aca = 0;
};
void add(Node* Trie, string& x, int i){
if(i == x.size()){
Trie -> aca = 1;
return;
}
if(Trie -> son.find(x[i]) == Trie -> son.end()){
// creo el Node del Nou caracter,
Trie-> son[x[i]] = new Node;
}
add(Trie->son[x[i]],x,i+1);
}
int pc = 0;
string mxs = "";
// La ultima paraula es la mes llarga
vc ans;
void dfs1(Node* u, int d, bool MX){
//cerr<<d<<" "<<mxs.size()<<endl;
//Processo mxs la ultima, per tant MX es si nomes si es el mxs
if(u->aca){
pc++; ans.pb('P');
}
bool f = false;
for(auto x : u->son){
if(MX && x.f == mxs[d]){
f = 1;
continue;
}
ans.pb(x.f);
dfs1(x.s,d+1,0);
if(pc!=n) ans.pb('-');
}
if(MX && f){
ans.pb(mxs[d]);
dfs1(u->son[mxs[d]],d+1,1);
if(pc!=n) ans.pb('-');
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
Node* st = new Node;
For(i,n,0){
string x; cin>>x;
if(x.size() > mxs.size()) mxs = x;
add(st,x,0);
}
// Exploro la Trie
dfs1(st,0,1);// 1 pq el nul forma part de mxs
cout<<ans.size()<<endl;
For(i,ans.size(),0) cout<<ans[i]<<endl;
}
Compilation message
printer.cpp: In function 'void add(Node*, std::string&, int)':
printer.cpp:34:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | if(i == x.size()){
| ~~^~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:23:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | #define For(i, n, x) for (int i = x; i < n; i++)
......
88 | For(i,ans.size(),0) cout<<ans[i]<<endl;
| ~~~~~~~~~~~~
printer.cpp:88:3: note: in expansion of macro 'For'
88 | For(i,ans.size(),0) cout<<ans[i]<<endl;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
2 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1748 KB |
Output is correct |
2 |
Correct |
6 ms |
2132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
5588 KB |
Output is correct |
2 |
Correct |
30 ms |
11880 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
13900 KB |
Output is correct |
2 |
Correct |
15 ms |
3284 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
34800 KB |
Output is correct |
2 |
Correct |
194 ms |
81232 KB |
Output is correct |
3 |
Correct |
111 ms |
40776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
26292 KB |
Output is correct |
2 |
Correct |
243 ms |
96608 KB |
Output is correct |
3 |
Correct |
125 ms |
46240 KB |
Output is correct |
4 |
Correct |
209 ms |
91096 KB |
Output is correct |