oj.uz

Submission #521814

# Submission time Handle Problem Language Result Execution time Memory
521814 2022-02-03T08:29:07 Z Shin Type Printer (IOI08_printer) C++14
100 / 100
 148 ms 99648 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK "task"
#define all(x) x.begin(), x.end()

const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct Node {
    Node *child[26];
    bool exist;
    int max_dist;

    Node() {
        for (int i = 0; i < 26; i ++)
            child[i] = nullptr;
        max_dist = 0;
    }
};

Node *root = new Node();

void dfs(Node *cur) {
    for (int c = 0; c < 26; c ++) {
        if (cur->child[c] == nullptr)
            continue;
        dfs(cur->child[c]);
        maximize(cur->max_dist, cur->child[c]->max_dist + 1);
    }
}

vector<char> oper;

void print(Node *cur, bool longest) {
    if (cur->exist) {
        oper.push_back('P');
    }

    bool ok = true;
    for (int c = 0; c < 26; c ++) {
        if (cur->child[c] == nullptr)
            continue;
        bool n_longest = longest & (cur->max_dist == cur->child[c]->max_dist + 1);
        if (!(n_longest & ok)) {
            oper.push_back(char (c + 'a'));
            print(cur->child[c], n_longest & ok);
        }
        if (n_longest) ok = false;
    }

    for (int c = 0; c < 26; c ++) {
        if (cur->child[c] == nullptr)
            continue;
        bool n_longest = longest & (cur->max_dist == cur->child[c]->max_dist + 1);
        if (n_longest) {
            oper.push_back(char (c + 'a'));
            print(cur->child[c], n_longest);
            break;
        }
    }
    if (!longest) oper.push_back('-');
}

void solve(void) {
    auto add = [&](string s) {
        Node *p = root;
        for (int i = 0; i < (int) s.size(); i ++) {
            int c = s[i] - 'a';
            if (p->child[c] == nullptr) p->child[c] = new Node();
            p = p->child[c];
        }
        p->exist = true;
    };

    int n; cin >> n;
    for (int i = 1; i <= n; i ++) {
        string s; cin >> s;
        add(s);
    }

    dfs(root);
    print(root, true);
    cout << oper.size() << '\n';
    for (char x: oper) cout << x << '\n';
}

signed main(void) {
    cin.tie(0)->sync_with_stdio(0);
    int test = 1;
//    cin >> test;
    while (test --) {
        solve();
    }
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5932 KB Output is correct
2 Correct 21 ms 12536 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14628 KB Output is correct
2 Correct 9 ms 3404 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 36460 KB Output is correct
2 Correct 123 ms 83640 KB Output is correct
3 Correct 68 ms 43176 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 28444 KB Output is correct
2 Correct 148 ms 99648 KB Output is correct
3 Correct 78 ms 49092 KB Output is correct
4 Correct 127 ms 94000 KB Output is correct