Always got TLE 43. I've tried different optimization on python, but nothing work. C++ with same code and std::getline optimization got AC with almost TLE 300-350msec. And as I see no one has AC with Python =\

5
2 0
1 3 0
2 0
5 0
4 0

I tried to solve this task by dp and bfs, but always have a TL on test 3.

what the data test 9

Even after reading all the posts here. Please help.
1. assert program is shorter than input
2. assert no long lines in source code
3. split string literal into vectors
4. assert no '\r' but '\n' after reading input
5. output with std::cout and '\n'
6. many tests and asserts

===this is an example of archive===
might be overkill to use Huffman and base64
shorten variable names in actual archive
===================================
//CPP
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

int length = 37;
std::vector<std::string> encoded{
"7VKh",
"7lg="
};
std::unordered_map<std::string, char> table{
{"00", 'o'},
{"01", 'l'},
{"100", 'w'},
{"1010", ' '},
{"1011", '!'},
{"1100", 'd'},
{"1101", 'e'},
{"1110", 'h'},
{"1111", 'r'}
};

struct HuffmanTree {
    char ch;
    struct HuffmanTree* left;
    struct HuffmanTree* right;
    ~HuffmanTree() {
        delete left;
        delete right;
    }
};

void build_tree(HuffmanTree* root, std::string code, char ch)
{
    auto node{root};
    for (auto x : code)
        if (x == '1') {
            if (node->right == nullptr)
                node->right = new HuffmanTree();
            node = node->right;
        } else {
            if (node->left == nullptr)
                node->left = new HuffmanTree();
            node = node->left;
        }
    node->ch = ch;
}

char lookup(std::vector<bool>::iterator& it, const HuffmanTree* tree)
{
    auto node{tree};
    while (true) {
        if (node->left == nullptr)
            break;
        if (*it)
            node = node->right;
        else
            node = node->left;
        it++;
    }
    return node->ch;
}

void huffman_decode(std::vector<bool> bits, const HuffmanTree* tree)
{
    auto it{bits.begin()};
    while (it != bits.end())
        std::cout << lookup(it, tree);
}

int six(char c)
{
    if (c >= 'A' and c <= 'Z')
        return c-'A';
    if (c >= 'a' and c <= 'z')
        return c-'a' + 26;
    if (c >= '0' and c <= '9')
        return c-'0' + 52;
    if (c == '+')
        return 62;
    if (c == '/')
        return 63;
    return 0;
}

std::vector<std::string> base64_decode(std::vector<std::string> encoded)
{
    std::vector<std::string> decoded;
    for (auto s : encoded) {
        std::string t;
        auto i{0u};
        while (i < s.size()) {
            auto p0{six(s[i])};
            auto p1{six(s[i+1])};
            auto p2{six(s[i+2])};
            auto p3{six(s[i+3])};
            t.push_back((p0<<2) + ((p1&0x30)>>4));
            if (s[i+2] != '=')
                t.push_back(((p1&0x0f)<<4) + ((p2&0x3c)>>2));
            if (s[i+3] != '=')
                t.push_back(((p2&0x03)<<6) + p3);
            i += 4;
        }
        decoded.push_back(t);
    }
    return decoded;
}

std::vector<bool> string_to_bits(int n, std::vector<std::string> v)
{
    std::vector<bool> bits;
    for (auto s : v)
        for (auto byte : s)
            for (auto i{7}; i >= 0; i--)
                bits.push_back((byte >> i) & 1);
    while (int(bits.size()) > n)
        bits.pop_back();
    return bits;
}

int main()
{
    auto decoded{base64_decode(encoded)};
    auto bits{string_to_bits(length, decoded)};
    auto root{new HuffmanTree()};
    for (auto [code, ch] : table)
        build_tree(root, code, ch);
    huffman_decode(bits, root);
}

Is there any way I can see the output of my program? The message "Runtime error" is very uninformative, besides, on my computer, my program performs a variety of tests without any errors.

Can you give me some tests,please?
I can't find any solutions on the internet.




Edited by author 03.05.2021 09:14

Tests?

Edited by author 03.11.2019 21:42

Edited by author 03.11.2019 21:42

Can you give me a test, please?

I changed my INF to 1e18 and got AC

Это пешки, а не дамки, поэтому они могут рубить только соседние фишки

There can't be -1, because you can always choose path k->2k->3k->k

Plz help me, I used hashing with binary search and got WA on 52.

3
1 1 1

Every subset must contain at least one element

Edited by author 26.01.2022 16:39

???
3

answer: zay

????a
4

answer: zayba

Edited by author 26.01.2022 08:53

Instead of writing this: vector<int> g[2001];

write this: vector<vector<int>> g;............g.resize(n + 1);

Edited by author 09.06.2022 23:22

I do here according to the test case description. But I need some hint what actually wanted in this problem.