Submission #226392

#	Time	Username	Problem	Language	Result	Execution time	Memory
226392		shahriarkhan	Type Printer (IOI08_printer)	C++14	100 / 100	172 ms	51308 KiB

printer

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10