oj.uz

답안 #226380

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
226380 2020-04-23T16:00:41 Z shahriarkhan Type Printer (IOI08_printer) C++14
20 / 100
 673 ms 18544 KB 
#include<bits/stdc++.h>
using namespace std ;

const int maxN = 5e5 + 5 ;

int nex[maxN][26] , dep[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] ;
    }
}

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]) ;
    }
    if(!p) 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:62: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

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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

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

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB Output is correct
2 Incorrect 5 ms 384 KB didn't print every word

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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