oj.uz

Submission #226392

# Submission time Handle Problem Language Result Execution time Memory
226392 2020-04-23T16:53:31 Z shahriarkhan Type Printer (IOI08_printer) C++14
100 / 100
 172 ms 51308 KB 
#include<bits/stdc++.h>
using namespace std ;

const int maxN = 5e5 + 5 ;

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

char s[25] ;

vector<char> ans ;

void insert_string()
{
    int v = 0 , siz = strlen(s) ;
    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 ;
    while(ed[ind]) ed[ind]-- , ans.push_back('P') ;
    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]) ;
        ans.push_back('-') ;
    }
}

int main()
{
    int n ;
    scanf("%d",&n) ;
    for(int i = 0 ; i < n ; ++i)
    {
        scanf("%s",s) ;
        insert_string() ;
    }
    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) printf("%c\n",ans[i]);
    return 0 ;
}

Compilation message

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

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 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #3
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 #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1024 KB Output is correct
2 Correct 8 ms 1408 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3328 KB Output is correct
2 Correct 23 ms 6656 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7796 KB Output is correct
2 Correct 13 ms 1920 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 19056 KB Output is correct
2 Correct 138 ms 42988 KB Output is correct
3 Correct 76 ms 22256 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14960 KB Output is correct
2 Correct 172 ms 51308 KB Output is correct
3 Correct 88 ms 25196 KB Output is correct
4 Correct 142 ms 48232 KB Output is correct