oj.uz

Submission #226388

# Submission time Handle Problem Language Result Execution time Memory
226388 2020-04-23T16:44:47 Z shahriarkhan Type Printer (IOI08_printer) C++14
80 / 100
 1000 ms 50540 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 ;
    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)
    {
        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
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 #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 1076 KB Output is correct
2 Correct 41 ms 1400 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 3448 KB Output is correct
2 Correct 229 ms 6648 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 7796 KB Output is correct
2 Correct 88 ms 1912 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 19056 KB Output is correct
2 Execution timed out 1084 ms 42672 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 15024 KB Output is correct
2 Execution timed out 1100 ms 50540 KB Time limit exceeded
3 Halted 0 ms 0 KB -