Submission #570459

#	Time	Username	Problem	Language	Result	Execution time	Memory
570459		SansPapyrus683	Burza (COCI16_burza)	C++17	160 / 160	60 ms	976 KiB

burza

#include <iostream>
#include <functional>
#include <vector>
#include <bitset>
#include <map>

// #include "debugging.h"

using std::cout;
using std::endl;
using std::vector;

// https://oj.uz/problem/view/COCI16_burza (input omitted due to length)
int main() {
    int node_num;
    int max_turns;
    std::cin >> node_num >> max_turns;
    vector<vector<int>> neighbors(node_num);
    for (int e = 0; e < node_num - 1; e++) {
        int n1, n2;
        std::cin >> n1 >> n2;
        neighbors[--n1].push_back(--n2);
        neighbors[n2].push_back(n1);
    }

    if (max_turns * max_turns >= node_num) {
        cout << "DA" << endl;
        return 0;
    }
 
    std::map<int, int> lost;
    vector<vector<int>> cutoff_cover(node_num);
    vector<vector<int>> depth_nodes(max_turns + 1);
    std::function<void(int, int, int)> process_nodes;
    process_nodes = [&] (int at, int prev, int depth) {
        depth_nodes[depth].push_back(at);
        if (depth == max_turns) {
            lost[at] = lost.size();
            cutoff_cover[at] = {at};
            return;  // we don't care about anything past this depth
        }
        for (int n : neighbors[at]) {
            if (n != prev) {
                process_nodes(n, at, depth + 1);
                cutoff_cover[at].insert(
                    cutoff_cover[at].end(),
                    cutoff_cover[n].begin(),
                    cutoff_cover[n].end()
                );
            }
        }
    };
    process_nodes(0, 0, 0);
    
    vector<std::pair<int, int>> intervals;
    for (const vector<int>& cc : cutoff_cover) {
        if (cc.empty()) {
            intervals.push_back({-1, -1});
        } else {
            intervals.push_back({lost[cc.front()] + 1, lost[cc.back()] + 1});
        }
    }

    vector<int> possible(1 << max_turns);
    possible[0] = 0;
    for (int ss = 1; ss < (1 << max_turns); ss++) {
        int& curr = possible[ss];
        for (int to_add = 0; to_add < max_turns; to_add++) {
            if ((ss & (1 << to_add)) != 0) {
                int prev = possible[ss & ~(1 << to_add)];
                for (int n : depth_nodes[to_add + 1]) {
                    if (intervals[n].first <= prev + 1) {
                        curr = std::max(curr, intervals[n].second);
                    }
                }
            }
        }
        // cout << std::bitset<2>(ss) << ' ' << possible[ss] << endl;

        if (possible[ss] == lost.size()) {
            cout << "DA" << endl;
            return 0;
        }
    }

    cout << "NE" << endl;
}

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:80:26: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::map<int, int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         if (possible[ss] == lost.size()) {

• Subtask 1: 16 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16