oj.uz

Submission #226383

# Submission time Handle Problem Language Result Execution time Memory
226383 2020-04-23T16:34:57 Z shahriarkhan Type Printer (IOI08_printer) C++14
20 / 100
 722 ms 18976 KB 
#include<bits/stdc++.h>
using namespace std ;

const int maxN = 5e5 + 5 ;

int nex[maxN][26] , dep[maxN] , ed[maxN] , sz ;

vector<char> ans ;

void insert_string(string &s)
{
    int v = 0 , siz = s.size() ;
    for(int i = 0 ; i < siz ; ++i)
    {
        int c = s[i]-'a' ;
        if(!nex[v][c]) nex[v][c] = ++sz ;
        v = nex[v][c] ;
    }
    ++ed[v] ;
}

int depth(int ind)
{
    int p = 0 ;
    for(int i = 0 ; i < 26 ; ++i)
    {
        if(nex[ind][i])
        {
            p = 1 ;
            dep[ind] = max(dep[ind],depth(nex[ind][i]) + 1) ;
        }
    }
    if(!p) dep[ind] = 1 ;
    return dep[ind] ;
}

void dfs(int ind)
{
    int p = 0 ;
    vector<pair<int,int> > vx ;
    for(int i = 0 ; i < 26 ; ++i)
    {
        if(nex[ind][i])
        {
            vx.push_back({dep[nex[ind][i]],i}) ;
            ++p ;
        }
    }
    sort(vx.begin(),vx.end()) ;
    for(int i = 0 ; i < p ; ++i)
    {
        char c = 'a' + vx[i].second ;
        ans.push_back(c) ;
        dfs(nex[ind][vx[i].second]) ;
    }
    while(ed[ind]) ed[ind]-- , ans.push_back('P') ;
    if(ind) ans.push_back('-') ;
}

int main()
{
    int n ;
    scanf("%d",&n) ;
    for(int i = 0 ; i < n ; ++i)
    {
        string s ;
        cin>>s ;
        insert_string(s) ;
    }
    depth(0) ;
    dfs(0) ;
    int siz = ans.size() ;
    while(ans[siz-1]!='P') --siz ;
    printf("%d\n",siz) ;
    for(int i = 0 ; i < siz ; ++i) cout<<ans[i]<<endl ;
    return 0 ;
}

Compilation message

printer.cpp: In function 'int main()':
printer.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n) ;
     ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 113 ms 3348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 280 ms 7772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 722 ms 18976 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 579 ms 14960 KB Output isn't correct
2 Halted 0 ms 0 KB -