#include<bits/stdc++.h>
using namespace std;
const int lmt=1e6;
int adj[lmt][26];
bool vis[lmt];
int depth[lmt];//int subtree[lmt];
int indx=1;
int cnt=0;
string ans;
void insert(string s,int now)
{
for(char c:s)
{
int num=c-'a';
if(adj[now][num]==0)
{
indx++;
adj[now][num]=indx;
now=indx;
}
else
{
now=adj[now][num];
}
}
vis[now]=1;
}
/*void getsubtree(int u)
{
subtree[u]=1;
for(int i=0;i<26;i++)
{
if(adj[u][i]!=0)
{
int v=adj[u][i];
getsubtree(v);
subtree[u]+=subtree[v];
}
}
}*/
void getdepth(int u)
{
depth[u]=1;
for(int i=0;i<26;i++)
{
if(adj[u][i]!=0)
{
getdepth(adj[u][i]);
depth[u]=max(depth[u],depth[adj[u][i]]+1);
}
}
}
void dfs(int u)
{
if(vis[u])
{
vis[u]=0;
ans+='P';
}
vector<pair<int,int>>p;
for(int i=0;i<26;i++)
{
if(adj[u][i]!=0)
{
p.push_back(make_pair(depth[adj[u][i]],i));
}
}
sort(p.begin(),p.end());
for(int i=0;i<p.size();i++)
{
char c='a'+p[i].second;
ans+=c;
dfs(adj[u][p[i].second]);
}
ans+='-';
}
int main()
{
//#ifndef ONLINE_JUDGE
// freopen("take.in","r",stdin);
// freopen("give.out","w",stdout);
//#endif
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
insert(s,1);
}
getdepth(1);
dfs(1);
reverse(ans.begin(),ans.end());
while(ans[0]=='-') ans.erase(ans.begin());
reverse(ans.begin(),ans.end());
cout<<ans.size()<<endl;
for(char c:ans) cout<<c<<endl;
}
Compilation message
printer.cpp: In function 'void dfs(int)':
printer.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();i++)
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
384 KB |
Output is correct |
2 |
Correct |
25 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
1152 KB |
Output is correct |
2 |
Correct |
42 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
3192 KB |
Output is correct |
2 |
Correct |
226 ms |
6652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
283 ms |
7688 KB |
Output is correct |
2 |
Correct |
88 ms |
2040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
682 ms |
18580 KB |
Output is correct |
2 |
Execution timed out |
1098 ms |
41648 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
552 ms |
14612 KB |
Output is correct |
2 |
Execution timed out |
1095 ms |
49324 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |