Submission #248430

#TimeUsernameProblemLanguageResultExecution timeMemory
248430DavidDamianType Printer (IOI08_printer)C++11
20 / 100
100 ms19476 KiB
#include <bits/stdc++.h> using namespace std; struct node{ int bucket[27]; int cnt; }; node trie[500005]; int act=0; void trieInsert(string s) { int u=0; for(int i=0;i<s.size();i++){ int letter=s[i]-'a'; if(trie[u].bucket[letter]==0) trie[u].bucket[letter]=++act; u=trie[u].bucket[letter]; } trie[u].cnt++; } int subtreeSize[500005]; void computeSize(int u) { subtreeSize[u]=1; for(int i=0;i<'z'-'a';i++){ if(trie[u].bucket[i]!=0){ int v=trie[u].bucket[i]; computeSize(v); subtreeSize[u]=max(subtreeSize[u],subtreeSize[u]+subtreeSize[v]); } } } struct order { int id,w; }; bool byW(order a,order b) { return a.w<b.w; } string ans; int printed_words=0; int n; void dfs(int u) { order A[27]; if(trie[u].cnt){ printed_words++; ans.push_back('P'); } for(int i=0;i<27;i++){ A[i].id=i; int v=trie[u].bucket[i]; A[i].w=(v!=0)? subtreeSize[v] : INT_MAX; } sort(A,A+27,byW); for(int i=0;i<'z'-'a';i++){ if(A[i].w==INT_MAX) continue; int v=trie[u].bucket[ A[i].id ]; if(v!=0){ ans.push_back(char(A[i].id+'a')); dfs(v); } } if(printed_words<n) ans.push_back('-'); } int main() { cin>>n; for(int i=1;i<=n;i++){ string s; cin>>s; trieInsert(s); } computeSize(0); dfs(0); cout<<ans.size()<<'\n'; for(char c: ans){ cout<<c<<'\n'; } return 0; }

Compilation message (stderr)

printer.cpp: In function 'void trieInsert(std::__cxx11::string)':
printer.cpp:12:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~
#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...