oj.uz

Submission #982743

# Submission time Handle Problem Language Result Execution time Memory
982743 2024-05-14T17:01:53 Z vjudge1 Type Printer (IOI08_printer) C++17
100 / 100
 111 ms 101120 KB 
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <iterator>
#include <utility>
using namespace std;

#define endl '\n'

typedef long long int ll;

int n;
vector<char> out;

class Node {
    public:
    Node* child[26];
    bool isEnd;
    bool isLast;
    Node(bool isEnd, bool isLast) {
        for (int i = 0; i < 26; i++) {
            this->child[i] = NULL;
        }
        this->isEnd = isEnd;
        this->isLast = isLast;
    }
};

void insertTrie(Node* root, string& str, bool isLongest) {
    int idx = 0;
    Node* curNode = root;
    while (idx < str.length()) {
        char chr = str[idx];
        int childIdx = (int) chr - (int)'a';
        if (curNode->child[childIdx] == NULL) {
            curNode->child[childIdx] = new Node(false, false);
        }
        curNode->child[childIdx]->isEnd = curNode->child[childIdx]->isEnd || (idx == str.length() - 1);
        curNode->child[childIdx]->isLast = isLongest;
        curNode = curNode->child[childIdx];
        idx++;
    }
}

void traverseTrie(Node *cur) {
    if (cur->isEnd) {
        out.push_back('P');
    }
    
    int last = -1;
    for (int i = 0; i < 26; i++) {
        if (cur->child[i] != NULL) {
            if (cur->child[i]->isLast) {
                last = i;
                continue;
            }
            char chr = (char) (i + (int) 'a');
            out.push_back(chr);
            traverseTrie(cur->child[i]);
            out.push_back('-');
        }
    }
    
    if (last != -1) {
        char chr = (char) (last + (int) 'a');
        out.push_back(chr);
        traverseTrie(cur->child[last]);
    }
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    cin >> n;
    vector<string> arr;
    int longest;
    int maxLen = 0;
    Node* root = new Node(false, true);
    for (int i = 0; i < n; i++) {
        arr.push_back("");
        cin >> arr[i];
        insertTrie(root, arr[i], false);
        if (maxLen < arr[i].length()) {
            maxLen = (int) arr[i].length();
            longest = i;
        }
    }
    insertTrie(root, arr[longest], true);
    traverseTrie(root);
    cout << out.size() << endl;
    for (int i = 0; i < out.size(); i++) {
        cout << out[i] << endl;
    }
    return 0;
}

Compilation message

printer.cpp: In function 'void insertTrie(Node*, std::string&, bool)':
printer.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while (idx < str.length()) {
      |            ~~~~^~~~~~~~~~~~~~
printer.cpp:45:83: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         curNode->child[childIdx]->isEnd = curNode->child[childIdx]->isEnd || (idx == str.length() - 1);
      |                                                                               ~~~~^~~~~~~~~~~~~~~~~~~
printer.cpp: In function 'int main()':
printer.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         if (maxLen < arr[i].length()) {
      |             ~~~~~~~^~~~~~~~~~~~~~~~~
printer.cpp:99:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for (int i = 0; i < out.size(); i++) {
      |                     ~~^~~~~~~~~~~~
printer.cpp:96:33: warning: 'longest' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     insertTrie(root, arr[longest], true);
      |                                 ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct
2 Correct 2 ms 2392 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6236 KB Output is correct
2 Correct 14 ms 12736 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 15316 KB Output is correct
2 Correct 9 ms 3800 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 37632 KB Output is correct
2 Correct 94 ms 85000 KB Output is correct
3 Correct 54 ms 45036 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 29640 KB Output is correct
2 Correct 111 ms 101120 KB Output is correct
3 Correct 63 ms 51184 KB Output is correct
4 Correct 94 ms 95556 KB Output is correct