oj.uz

Submission #226244

# Submission time Handle Problem Language Result Execution time Memory
226244 2020-04-23T07:55:08 Z shaf_wa_nur Type Printer (IOI08_printer) C++14
30 / 100
 200 ms 83816 KB 
#include <bits/stdc++.h>
using namespace std;

struct node {
    node *child[26];
    int sub;
    bool isEnd = false;
};

node *make() {
    node *u = new node;
    for (int i = 0; i < 26; i++) {
        u->child[i] = nullptr;
    }
    u->sub = 0;
    u->isEnd = false;
    return u;
}

void insert(node *root, string s) {
    node *u = root;
    for (char c : s) {
        int idx = c - 'a';
        if (u->child[idx] == nullptr) {
            u->child[idx] = make();
        }
        u = u->child[idx];
    }
    u->isEnd = true;
}

void dfs(node *root) {
    node *u = root;
    u->sub = 1;
    for (int i = 0; i < 26; i++) {
        if (u->child[i] != nullptr) {
            dfs(u->child[i]);
            u->sub += u->child[i]->sub;
        }
    }
}

vector<char> op;

void go(node *root) {
    node *u = root;
    if (u->isEnd) op.push_back('P');
    vector<int> ord;
    for (int i = 0; i < 26; i++) {
        if (u->child[i] == nullptr) continue;
        ord.push_back(i);
    }
    sort(ord.begin(), ord.end(), [&] (int i, int j) {
        return u->child[i]->sub < u->child[j]->sub;
    });
    int cnt = 1;
    for (int i : ord) {
        op.push_back(i + 'a');
        ++cnt;
        go(u->child[i]);
    }
    op.push_back('-');
}

int main() { 
    ios_base::sync_with_stdio(0); 
    cin.tie(0);
    node *root = make(); 
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        insert(root, s);
    }
    dfs(root);
    go(root);
    while (op.back() == '-') op.pop_back();
    cout << (int) op.size() << '\n';
    for (char c : op) {
        cout << c << '\n';
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1920 KB Output is correct
2 Incorrect 9 ms 2304 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 6016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 14748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 36468 KB Output is correct
2 Correct 200 ms 83816 KB Output is correct
3 Incorrect 105 ms 43244 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 28532 KB Output isn't correct
2 Halted 0 ms 0 KB -