oj.uz

Submission #390512

# Submission time Handle Problem Language Result Execution time Memory
390512 2021-04-16T08:53:44 Z ngpin04 Type Printer (IOI08_printer) C++14
100 / 100
 302 ms 72180 KB 
#include <bits/stdc++.h>

using namespace std;

struct trie {

    int node;
    vector <vector <int>> ptr;
    vector <int> dep;
    vector <bool> word;

    trie(int n)
    {
        ptr.assign(n + 5, vector <int> (26, 0));
        dep.assign(n + 5, 0);
        word.assign(n + 5, 0);
    }

    void add(const string &s)
    {
        int cur = 0;
        int cnt = s.size();
        for (char c : s) {
            int &p = ptr[cur][c - 'a'];
            if (!p)
                p = ++node;
            cur = p;
            dep[cur] = max(dep[cur], cnt--);
        }
        word[cur] = true;
    }

    void dfs(int u, string &ans)
    {
        vector <int> id(26); iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j) {
            return dep[ptr[u][i]] < dep[ptr[u][j]];
        });
        if (word[u])
            ans += 'P';
        for (int i : id) {
            int v = ptr[u][i];
            if (v == 0)
                continue;
            ans += 'a' + i;
            dfs(v, ans);
            ans += '-';
        }
    }
};

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("file.inp","r",stdin);
    trie tree(500000);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        tree.add(s);
    }
    string ans;
    tree.dfs(0, ans);
    while (ans.back() == '-')
        ans.pop_back();
    cout << ans.size() << "\n";
    for (char c : ans)
        cout << c << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 68860 KB Output is correct
2 Correct 57 ms 68856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 68744 KB Output is correct
2 Correct 55 ms 68752 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 68804 KB Output is correct
2 Correct 56 ms 68776 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 68800 KB Output is correct
2 Correct 55 ms 68820 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 68872 KB Output is correct
2 Correct 57 ms 68888 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 68924 KB Output is correct
2 Correct 61 ms 68932 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 68996 KB Output is correct
2 Correct 83 ms 69316 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 69332 KB Output is correct
2 Correct 67 ms 69156 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 69996 KB Output is correct
2 Correct 264 ms 71732 KB Output is correct
3 Correct 162 ms 70496 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 69804 KB Output is correct
2 Correct 302 ms 72180 KB Output is correct
3 Correct 180 ms 70752 KB Output is correct
4 Correct 279 ms 71944 KB Output is correct