Submission #521814

#	Time	Username	Problem	Language	Result	Execution time	Memory
521814		Shin	Type Printer (IOI08_printer)	C++14	100 / 100	148 ms	99648 KiB

printer

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10