oj.uz

Submission #546177

# Submission time Handle Problem Language Result Execution time Memory
546177 2022-04-06T15:16:50 Z smth Type Printer (IOI08_printer) C++14
100 / 100
 150 ms 106316 KB 
#include<iostream>
#include<vector>
#define endl '\n'
using namespace std;
char res[1000000];
int len=0;
struct trie
{
    trie* chil[27];
    bool word;
    int dep;
    trie()
    {
        for(int i=0;i<27;i++)chil[i]=NULL;
        word = 0;
        dep = 0;
    }
};
trie* root = new trie;

void add(trie* curr, string& word, int ind)
{

    if(ind==word.size())
    {
        curr->word=true;
        return;
    }
    int let=word[ind]-'a';
    if(curr->chil[let]==NULL)curr->chil[let]=new trie;

    add(curr->chil[let], word, ind+1);

    curr->dep = max(curr->dep, curr->chil[let]->dep+1);

}
void sear(trie* curr, int ind)
{
    if(curr==NULL)
    {
        return;
    }
    if(curr->word==true)res[len++]='P';

    int maxi=0;

    for(int i=0;i<27;i++){

           if(curr->chil[i]!=NULL) {maxi=max(maxi,curr->chil[i]->dep); }
    }
    for(int i=0;i<27;i++){

           if(curr->chil[i]!=NULL && curr->chil[i]->dep!=maxi) { res[len++]=char(i+'a');sear(curr->chil[i],ind+1);}
    }
     for(int i=0;i<27;i++){

           if(curr->chil[i]!=NULL && curr->chil[i]->dep==maxi) { res[len++]=char(i+'a');sear(curr->chil[i],ind+1);}
    }


    res[len++]='-';

}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long n, q, i, j, t, k,x,ind=0;
    string s1, s;

    cin>>n;

    while(n--)
    {
       cin>>s;
       add(root,s,0);
    }
    sear(root, 0);

    for(i=len-1;i>=0;i--)
    {
        if(res[i]!='-')break;
    } ind =i;
    cout<<ind+1<<endl;
    for(i=0;i<=ind;i++)cout<<res[i]<<endl;

}

Compilation message

printer.cpp: In function 'void add(trie*, std::string&, int)':
printer.cpp:24:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     if(ind==word.size())
      |        ~~~^~~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:70:18: warning: unused variable 'q' [-Wunused-variable]
   70 |     long long n, q, i, j, t, k,x,ind=0;
      |                  ^
printer.cpp:70:24: warning: unused variable 'j' [-Wunused-variable]
   70 |     long long n, q, i, j, t, k,x,ind=0;
      |                        ^
printer.cpp:70:27: warning: unused variable 't' [-Wunused-variable]
   70 |     long long n, q, i, j, t, k,x,ind=0;
      |                           ^
printer.cpp:70:30: warning: unused variable 'k' [-Wunused-variable]
   70 |     long long n, q, i, j, t, k,x,ind=0;
      |                              ^
printer.cpp:70:32: warning: unused variable 'x' [-Wunused-variable]
   70 |     long long n, q, i, j, t, k,x,ind=0;
      |                                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1916 KB Output is correct
2 Correct 4 ms 2388 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6332 KB Output is correct
2 Correct 21 ms 13260 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 15572 KB Output is correct
2 Correct 9 ms 3540 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 39000 KB Output is correct
2 Correct 127 ms 89332 KB Output is correct
3 Correct 72 ms 46028 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 30448 KB Output is correct
2 Correct 150 ms 106316 KB Output is correct
3 Correct 82 ms 52260 KB Output is correct
4 Correct 138 ms 100296 KB Output is correct