oj.uz

Submission #716347

# Submission time Handle Problem Language Result Execution time Memory
716347 2023-03-29T17:57:10 Z kartapolov Type Printer (IOI08_printer) C++14
0 / 100
 169 ms 43892 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define print(x) cout << #x << " = " << x << endl;
#define input(vec) for (size_t i = 0; i < vec.size(); i++) cin >> vec[i];

const long long MOD = 1000000000 + 7;

using namespace std;
using ll = long long;

vector<char> ans;

class BOR {
    struct Node {
        vector<Node*> kids = vector<Node*>(26, nullptr);
        bool isTerminal = false;
        bool isLeave = true;
        int length = 1000;
    };

public:
    Node *head = new Node();

    void add(Node *cur, int i, string& s) {
        if (i == s.size()) {
            cur->isTerminal = true;
            return;
        }

        if (cur->kids[s[i] - 'a'] == nullptr) {
            cur->kids[s[i] - 'a'] = new Node();
            cur->isLeave = false;
        }

        add(cur->kids[s[i] - 'a'], i + 1, s);
    }

    void output(Node *cur, char data) {
        if (cur == nullptr) return;

        for (int i = 0 ; i < 26; i++) output(cur->kids[i], 'a' + i);
        cout << data << "->"<<cur->isTerminal<<"->" << cur->length << ' ';
    }

    int whatLength(Node *cur) {
        return (cur == nullptr ? 0 : cur->length);
    }

    void count(Node *cur) {
        if (cur == nullptr) return;

        if (cur->isLeave) {
            cur->length = 1;
            return;
        }

        for (auto kid : cur->kids) count(kid);

        for (auto kid : cur->kids) cur->length = max(cur->length, whatLength(kid) + 1);
        return;
    }

    void count() {
        count(this->head);
        return;
    }

    void dfs(Node *cur, char data) {
        if (cur == nullptr) return;

        ans.push_back(data);
        if (cur->isTerminal) ans.push_back('P');

        vector<pair<int, int>> fake(cur->kids.size());
        for (int i = 0; i < cur->kids.size(); i++)
            fake[i] = {whatLength(cur->kids[i]), i};
        sort(fake.begin(), fake.end());

        for (int i = 0; i < fake.size(); i++) dfs(cur->kids[fake[i].second], 'a' + fake[i].second);

        ans.push_back('-');
        return;
        }
};

void solve(BOR& S) {
    int n, t; cin >> n; t = n;
    while (t--) {
        string s; cin >> s;
        S.add(S.head, 0, s);
    }
    S.count();
    //S.output(S.head, '*'); cout << endl;
    S.dfs(S.head, '*');
    for (auto i : ans) cout << i << " ";
    // int q = 0;
    // for (int i = ans.size(); i >= 0 && ans[i] != 'P'; i--) q++;
    // cout << ans.size() - q << '\n';
    // for (int i = 1; i <= ans.size() - q; i++)
    //     cout << ans[i] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    BOR S;
    //int t=1; //cin >> t;
    /*while (t--) */solve(S);
    return 0;
}

Compilation message

printer.cpp: In member function 'void BOR::add(BOR::Node*, int, std::string&)':
printer.cpp:28:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         if (i == s.size()) {
      |             ~~^~~~~~~~~~~
printer.cpp: In member function 'void BOR::dfs(BOR::Node*, char)':
printer.cpp:78:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<BOR::Node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for (int i = 0; i < cur->kids.size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~~
printer.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int i = 0; i < fake.size(); i++) dfs(cur->kids[fake[i].second], 'a' + fake[i].second);
      |                         ~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Expected integer, but "*" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Expected integer, but "*" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Expected integer, but "*" found
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Expected integer, but "*" found
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 468 KB Expected integer, but "*" found
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2132 KB Expected integer, but "*" found
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 7024 KB Expected integer, but "*" found
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 17676 KB Expected integer, but "*" found
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 43892 KB Expected integer, but "*" found
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 34292 KB Expected integer, but "*" found
2 Halted 0 ms 0 KB -