# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
116713 | tselmegkh | Type Printer (IOI08_printer) | C++14 | 163 ms | 98552 KiB |
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>
using namespace std;
#define INF 1e9
#define MAX 100005
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define ull long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define nl '\n'
#define zai <<' '<<
#define all(a) a.begin(),a.end()
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
int total;
struct Trie{
bool islast;
bool isleaf;
Trie *next[26];
Trie(){
for(int i=0;i<26;i++){
next[i]=NULL;
islast=0;
isleaf=0;
}
}
};
void insert(Trie* root,string str,int sz){
for(int i=0;i<sz;i++){
if(root->next[str[i]-'a']==NULL){
root->next[str[i]-'a']=new Trie();
total+=2;
}
root=root->next[str[i]-'a'];
}
root->isleaf=1;
}
void longestmark(Trie* root,string word){
for(int i=0;i<word.size();i++){
root->next[word[i]-'a']->islast=1;
root=root->next[word[i]-'a'];
}
}
void Print(Trie* root){
for(int i=0;i<26;i++){
if(root->next[i]!=NULL && !root->next[i]->islast){
cout << char(i+'a') << nl;
if(root->next[i]->isleaf){
cout << "P" << nl;
}
Print(root->next[i]);
cout << "-" << nl;
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
string word,longest="";
cin >> n;
Trie *root=new Trie();
int printtimes=n;
while(n--){
cin >> word;
if(word.size()>longest.size()){
longest=word;
}
insert(root,word,word.size());
}
longestmark(root,longest);
cout << total-longest.size()+printtimes << nl;
Print(root);
for(int i=0;i<longest.size();i++){
cout << longest[i] << nl;
Print(root->next[longest[i]-'a']);
if(root->next[longest[i]-'a']->isleaf){
cout << "P" << nl;
}
root=root->next[longest[i]-'a'];
}
return 0;
}
Compilation message (stderr)
# | 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... |