oj.uz

Submission #703306

# Submission time Handle Problem Language Result Execution time Memory
703306 2023-02-26T23:26:29 Z Pietra Type Printer (IOI08_printer) C++14
100 / 100
 162 ms 56772 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 716 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1108 KB Output is correct
2 Correct 3 ms 1364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3540 KB Output is correct
2 Correct 22 ms 7384 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 8540 KB Output is correct
2 Correct 9 ms 2132 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 20768 KB Output is correct
2 Correct 134 ms 47688 KB Output is correct
3 Correct 80 ms 24868 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 16384 KB Output is correct
2 Correct 162 ms 56772 KB Output is correct
3 Correct 105 ms 28096 KB Output is correct
4 Correct 156 ms 53576 KB Output is correct