oj.uz

Submission #850065

# Submission time Handle Problem Language Result Execution time Memory
850065 2023-09-15T17:04:42 Z dshfjka Type Printer (IOI08_printer) C++14
0 / 100
 195 ms 28352 KB 
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int MAX_N = 500001;
const int ALPHABET_SIZE = 26;

struct Trie {
    struct Node {
        int child[ALPHABET_SIZE];
        int cnt;
    };
    vector<Node> t;

    Trie() {
        t.emplace_back();
    }

    void insert(int depth, int pos, const string &s) {
        if (depth == s.length()) {
            t[pos].cnt++;
            return;
        }

        if (!t[pos].child[s[depth] - 'a']) {
            t[pos].child[s[depth] - 'a'] = t.size();
            t.emplace_back();
        }

        insert(depth + 1, t[pos].child[s[depth] - 'a'], s);
    }

    void query(int pos, vector<char> &v) {
        vector<int> stack;
        stack.push_back(pos);

        while (!stack.empty()) {
            int curPos = stack.back();
            stack.pop_back();

            for (int i = 0; i < ALPHABET_SIZE; i++) {
                if (t[curPos].child[i]) {
                    char ch = i + 'a';
                    v.push_back(ch);

                    if (t[curPos].cnt > 0)
                        v.insert(v.end(), t[curPos].cnt, 'P');

                    stack.push_back(t[curPos].child[i]);
                }
            }
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    Trie trie;

    for (int i = 0; i < n; i++) {
        string x;
        cin >> x;
        trie.insert(0, 0, x);
    }

    vector<char> v;
    trie.query(0, v);
    cout << v.size() << endl;

    for (char a : v)
        cout << a << endl;

    return 0;
}

Compilation message

printer.cpp: In member function 'void Trie::insert(int, int, const string&)':
printer.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         if (depth == s.length()) {
      |             ~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB didn't print every word
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 600 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1316 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 3852 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 8520 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 28352 KB printed invalid word
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 15556 KB printed invalid word
2 Halted 0 ms 0 KB -