Submission #850054

#TimeUsernameProblemLanguageResultExecution timeMemory
850054dshfjkaType Printer (IOI08_printer)C++14
100 / 100
998 ms57788 KiB
#include <bits/stdc++.h> #define LL long long 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{ int child[26]; }; 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[s[depth]-'a']){ t[pos].child[s[depth]-'a']=t.size(); t.emplace_back(); } insert(depth+1,t[pos].child[s[depth]-'a'],s); dp[pos]=max(dp[pos],dp[t[pos].child[s[depth]-'a']]+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,ket=-1; for(int i=0;i<cnt[pos];i++)v.push_back('P'); if(status==1) { for(int a=0;a<26;a++) { if(t[pos].child[a]) { if(dp[t[pos].child[a]]>maks) { maks=dp[t[pos].child[a]]; ket=a; } } } } // printf("maks=%d dan ket=%c\n",maks,ket+'a'); for(int a=0;a<26;a++) { if(t[pos].child[a] && ket!=a) { masuk=1; // printf("MASUK dengan %c \n",a+'a'); masuk=1; v.push_back(a+'a'); query(t[pos].child[a],0); v.push_back('-'); } } if(status && ket!=-1) { masuk=1; v.push_back(ket+'a'); 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:20:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   if(depth==s.length())
      |      ~~~~~^~~~~~~~~~~~
printer.cpp: In member function 'void Trie::query(int, bool)':
printer.cpp:37:8: warning: variable 'masuk' set but not used [-Wunused-but-set-variable]
   37 |   bool masuk=0;
      |        ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...