oj.uz

Submission #851071

# Submission time Handle Problem Language Result Execution time Memory
851071 2023-09-18T13:17:20 Z assem_albitar Type Printer (IOI08_printer) C++17
100 / 100
 288 ms 175840 KB 
#include <bits/stdc++.h>
#define ll long long
#define all(v)   v.begin(), v.end()
#define F first
#define S second
#define assem ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=400200;
string getString()
{
    char c[(int)50];
    scanf("%s", c);
    return c;
}
vector<char> an;
int n,al;
vector<string> v;
struct trie
{
    int sum,pr;
    bool f;
    vector<char> a;
    int ans[26];
    trie* child[26];
    trie()
    {
        sum=f=pr=0;
        memset(child,0,sizeof child);
        memset(ans,1e9,sizeof ans);
    }
    void add(int i,int j,int sz)
    {
        if(j==sz)
        {
            f=1;
            return;
        }
        if(child[v[i][j]-'a']==0)
        {
            child[v[i][j]-'a']=new trie();
            a.push_back(v[i][j]);
        }
        child[v[i][j]-'a']->add(i,j+1,sz);
    }
    void help()
    {
        pr=2+f;
        for(int i=0;i<26;i++)if(child[i]!=0)child[i]->help(),pr+=child[i]->pr,sum+=child[i]->pr;
    }
    int get()
    {
        int mn=1e9;
        for(int i=0;i<a.size();i++)
        {
            ans[a[i]-'a']=child[a[i]-'a']->get()+sum-child[a[i]-'a']->pr+1;
            mn=min(mn,ans[a[i]-'a']);
        }
        if(mn==1e9)mn=f;
        else mn=mn+f;
        return mn;
    }
    void lp()
    {
        if(f)
        {
            an.push_back('P');
        }
        for(int i=0;i<26;i++)
        {
            if(child[i]!=0)
            {
                an.push_back((char)(i+'a'));
                child[i]->lp();
                an.push_back('-');
            }
        }
    }
    void prl()
    {
        if(f)an.push_back('P');
        int mn1=1e9,id=0;
        for(int i=0;i<26;i++)
        {
            if(child[i]!=0)
            {
                if(mn1>ans[i])
                {
                    mn1=ans[i];
                    id=i;
                }
            }
        }
        for(int i=0;i<26;i++)
        {
            if(child[i]!=0&&i!=id)
            {
                an.push_back((char)('a'+i));
                child[i]->lp();
                an.push_back('-');
            }
        }
        if(mn1!=1e9)
        {
            an.push_back((char)(id+'a'));
            child[id]->prl();
        }

    }
};
int main()
{
    scanf("%d",&n);
    trie* root=new trie();
    for(int i=0; i<n; i++)
    {
        string q;
        q=getString();
        v.push_back(q);
        root->add(i,0,q.size());
    }
    root->help();
    root->pr-=2;
    int e=root->get();
    //printf("%d\n",root->pr);
    root->prl();
    int nn=an.size();
    cout<<nn<<endl;
    for(int i=0; i<nn; i++)
    {
        printf("%c\n",an[i]);
    }
}

Compilation message

printer.cpp: In constructor 'trie::trie()':
printer.cpp:27:17: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   27 |         sum=f=pr=0;
      |               ~~^~
printer.cpp: In member function 'int trie::get()':
printer.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int i=0;i<a.size();i++)
      |                     ~^~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:123:9: warning: unused variable 'e' [-Wunused-variable]
  123 |     int e=root->get();
      |         ^
printer.cpp: In function 'std::string getString()':
printer.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%s", c);
      |     ~~~~~^~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 10328 KB Output is correct
2 Correct 31 ms 22028 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 25800 KB Output is correct
2 Correct 10 ms 6096 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 64448 KB Output is correct
2 Correct 251 ms 147956 KB Output is correct
3 Correct 124 ms 76740 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 50420 KB Output is correct
2 Correct 288 ms 175840 KB Output is correct
3 Correct 138 ms 86976 KB Output is correct
4 Correct 260 ms 165968 KB Output is correct