oj.uz

Submission #59199

# Submission time Handle Problem Language Result Execution time Memory
59199 2018-07-21T06:00:50 Z TAMREF Type Printer (IOI08_printer) C++11
100 / 100
 361 ms 53616 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){
    //printf("sort_by_height(%d, %c)\n",x,trie[x].now);
    node &nd = trie[x];
    /*
    for(int i = 0; i < 26; i++){
        if(nd.nxt[i]) printf("link : (%d, %d)\n",i,nd.nxt[i]);
    }
    */
    //printf("DFS start - %d\n",x);
    for(int i = 0, u; i < 26; i++){
        u = nd.nxt[i];
        if(u) dfs_sort_by_height(u);
    }
    //printf("DFS end - %d\n",x);
    //printf("Sorting... %d\n",x);
    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;
         });
    //printf("Sorting finished %d\n",x);
    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(){
    //freopen("sample.txt","rt",stdin);
    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 248 KB Output is correct
2 Correct 2 ms 488 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 720 KB Output is correct
2 Correct 5 ms 1084 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1584 KB Output is correct
2 Correct 11 ms 1756 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3688 KB Output is correct
2 Correct 51 ms 7180 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8420 KB Output is correct
2 Correct 23 ms 8420 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 19932 KB Output is correct
2 Correct 277 ms 44372 KB Output is correct
3 Correct 167 ms 44372 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 44372 KB Output is correct
2 Correct 310 ms 53616 KB Output is correct
3 Correct 232 ms 53616 KB Output is correct
4 Correct 361 ms 53616 KB Output is correct