oj.uz

Submission #59202

# Submission time Handle Problem Language Result Execution time Memory
59202 2018-07-21T06:07:22 Z TAMREF Type Printer (IOI08_printer) C++11
100 / 100
 322 ms 51556 KB 
#include <bits/stdc++.h>
using namespace std;

const int mx = 25000 * 20 + 5;
const int root = 0;
const int hi = 25;

struct node{
    bool is_leaf;
    char now;
    int nxt[26];
    int hei;
} trie[mx];

int num_trie = root;

void trie_insert(string& S){
    int now = root;
    for(char &c : S){
        int &nxt = trie[now].nxt[c - 'a'];
        if(!nxt){
            nxt = ++num_trie;
        }
        now = nxt;
        trie[nxt].now = c;
    }
    trie[now].is_leaf = true;
}

void dfs_sort_by_height(int x){
    node &nd = trie[x];
    for(int i = 0, u; i < 26; i++){
        u = nd.nxt[i];
        if(u) dfs_sort_by_height(u);
    }
    stable_sort(nd.nxt, nd.nxt + 26, [](const int &u, const int &v)->bool{
            if(u == 0 || v == 0){
                return u == 0;
            }
            return trie[u].hei < trie[v].hei;
         });
    int highest_child = nd.nxt[hi];

    if(highest_child){
        nd.hei = trie[highest_child].hei + 1;
    }
}

string ans;
void dfs_solve(int x){
    node &nd = trie[x];

    if(nd.is_leaf) ans += 'P';

    for(int i = 0; i < 26; i++){
        int nxt = nd.nxt[i];
        if(nxt){
            ans += trie[nxt].now;
            dfs_solve(nxt);
        }
    }

    if(nd.now) ans += '-';
}

int n;
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    string S;
    for(int  i = 0; i < n; i++){
        cin >> S;
        trie_insert(S);
    }
    dfs_sort_by_height(root);
    dfs_solve(root);

    while(!ans.empty() && ans.back() == '-') ans.pop_back();

    cout << ans.size() << '\n';
    for(char &c : ans) cout << c << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 620 KB Output is correct
2 Correct 5 ms 956 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1384 KB Output is correct
2 Correct 8 ms 1656 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3576 KB Output is correct
2 Correct 45 ms 6920 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8088 KB Output is correct
2 Correct 18 ms 8088 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 19284 KB Output is correct
2 Correct 291 ms 43364 KB Output is correct
3 Correct 132 ms 43364 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 43364 KB Output is correct
2 Correct 322 ms 51556 KB Output is correct
3 Correct 166 ms 51556 KB Output is correct
4 Correct 320 ms 51556 KB Output is correct