Submission #703306

#	Time	Username	Problem	Language	Result	Execution time	Memory
703306		Pietra	Type Printer (IOI08_printer)	C++14	100 / 100	162 ms	56772 KiB

printer

#include<bits/stdc++.h>
using namespace std ; 

const int maxn = 28*25005  ; 

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" ; 

}

Compilation message (stderr)

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: 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