oj.uz

Submission #703305

# Submission time Handle Problem Language Result Execution time Memory
703305 2023-02-26T23:24:33 Z Pietra Type Printer (IOI08_printer) C++14
0 / 100
 67 ms 21008 KB 
#include<bits/stdc++.h>
using namespace std ; 

const int maxn = 2e5 + 5 ; 

int n, ct, pal ; 
int node[maxn][28], fim[maxn], f[maxn], dp[maxn] ; // node[v][u] - prox no partindo de v com aresta de letra u 
vector<char> ans ; 

void add(string s){
    int root = 0 ; 
    for(int i = 0 ; i < s.size() ; i++){
        if(!node[root][s[i]-'a']) node[root][s[i]-'a'] = ++ct ; 
        f[node[root][s[i]-'a']]++ ; 
        root = node[root][s[i]-'a'] ; 
    }
    fim[root] = 1 ; // nesse nó termina alguma palavra 
}

void dfs_alt(int v, int p){
    
    dp[v] = 1 ; 

    for(char i = 'a' ; i <= 'z' ; i++){
        if(!node[v][i-'a'] || node[v][i-'a'] == p) continue ; 
        dfs_alt(node[v][i-'a'], v) ; 
        dp[v] = max(dp[v], dp[node[v][i-'a']] + 1) ; 
    }

}

void dfs_ans(int v, int p){

    if(fim[v]){
        ans.push_back('P') ; 
        pal++ ; 
    }

    int mx = 0, id = -1 ; char mxx = 'a' ; 

    for(char i = 'a' ; i <= 'z' ; i++){
        int nxt = node[v][i-'a'] ; 
        if(nxt == 0 || nxt == p) continue ; 
        if(mx < dp[nxt]){
            mx = dp[nxt] ; mxx = i ; id = nxt ; 
        }
    }

    for(char i = 'a' ; i <= 'z' ; i++){
        int nxt = node[v][i-'a'] ; 
        if(nxt == 0 || nxt == p || id == nxt) continue ;
        ans.push_back(i) ; 
        dfs_ans(nxt, v) ; 
    }

    if(id != -1){
        ans.push_back(mxx) ; 
        //cout << mxx << "\n" ; 
        dfs_ans(id, v) ;  
    }

    if(pal != n) ans.push_back('-') ; 

}

// void dfs_view(int v, int p){
//     for(char i = 'a' ; i <= 'z' ; i++){
//         if(!node[v][i-'a']) continue ;
//         cout << v << " " << i << " " << node[v][i-'a'] << " " << dp[node[v][i-'a']] << "\n" ;
//         dfs_view(node[v][i-'a'], v) ;  
//     }
// }

int main(){

    ios_base::sync_with_stdio(false) ; cin.tie(NULL) ; 
    
    cin >> n ; 

    for(int i = 1 ; i <= n ; i++){
        string s ; cin >> s ; add(s) ; 
    }

    dfs_alt(0, 0) ; 

    dfs_ans(0, 0) ; 

    // dfs_view(0, 0) ; 

    cout << ans.size() << "\n" ; 
    for(auto a : ans) cout << a << "\n" ; 
    cout << "\n" ; 

}

Compilation message

printer.cpp: In function 'void add(std::string)':
printer.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i = 0 ; i < s.size() ; i++){
      |                     ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 328 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1108 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3536 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 8532 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 21008 KB Expected EOF
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 16460 KB Expected EOF
2 Halted 0 ms 0 KB -