oj.uz

답안 #851069

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851069 2023-09-18T13:12:14 Z assem_albitar Type Printer (IOI08_printer) C++17
30 / 100
 80 ms 63176 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');
            return;
        }
        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",e);
    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:124:9: warning: unused variable 'e' [-Wunused-variable]
  124 |     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:113:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB didn't print every word
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 3004 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 10076 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 25332 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 80 ms 63176 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 49348 KB didn't print every word
2 Halted 0 ms 0 KB -