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>
#define LL long long
#define fi first
#define se second
using namespace std;
vector<char>v;
int dp[500001];
// kata terpanjang dimaksukin nanti aja bos
int cnt[500001];
struct Trie{
int masuk=0;
struct node{
map<char,int>child;
};
vector<node>t;
Trie(){
t.emplace_back();
}
void insert(int depth ,int pos,const string& s)
{
if(depth==s.length())
{
cnt[pos]++;
return;
}
if(!t[pos].child.count(s[depth])){
t[pos].child[s[depth]]=t.size();
t.emplace_back();
}
int jeje=t[pos].child[s[depth]];
insert(depth+1,jeje,s);
dp[pos]=max(dp[pos],dp[jeje]+1);
// t[pos].cnt++;
}
void query( int pos, bool status)
{
// if(++masuk ==60)exit(0);
// cout<<"pos :"<<pos<<" status :"<<status<<endl;
bool masuk=0;
int maks=-1;
char ket;
for(int i=0;i<cnt[pos];i++)v.push_back('P');
if(status==1)
{
for(pair<char,int>a:t[pos].child)
{
if(dp[a.se]>maks)
{
maks=dp[a.se];
ket=a.fi;
}
}
}
// printf("maks=%d dan ket=%c\n",maks,ket+'a');
for(pair<char,int>a:t[pos].child)
{
if(ket!=a.fi)
{
// printf("MASUK dengan %c \n",a+'a');
v.push_back(a.fi);
query(a.se,0);
v.push_back('-');
}
}
if(status && maks!=-1)
{
v.push_back(ket);
query(t[pos].child[ket],1);
}
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
Trie trie;
for(int a=1;a<=n;a++)
{
string x;
cin>>x;
trie.insert(0,0,x);
}
trie.query(0,1);
cout<<v.size()<<endl;
for(char a:v)cout<<a<<endl;
}
Compilation message (stderr)
printer.cpp: In member function 'void Trie::insert(int, int, const string&)':
printer.cpp:22:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | if(depth==s.length())
| ~~~~~^~~~~~~~~~~~
printer.cpp: In member function 'void Trie::query(int, bool)':
printer.cpp:40:8: warning: unused variable 'masuk' [-Wunused-variable]
40 | bool masuk=0;
| ^~~~~
# | 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... |