oj.uz

Submission #570459

# Submission time Handle Problem Language Result Execution time Memory
570459 2022-05-30T02:52:43 Z SansPapyrus683 Burza (COCI16_burza) C++17
160 / 160
 60 ms 976 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 55 ms 876 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 872 KB Output is correct
2 Correct 54 ms 876 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 57 ms 852 KB Output is correct
6 Correct 1 ms 308 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 976 KB Output is correct
2 Correct 53 ms 884 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 496 KB Output is correct
2 Correct 50 ms 876 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 852 KB Output is correct
2 Correct 54 ms 868 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 304 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 884 KB Output is correct
2 Correct 49 ms 872 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 872 KB Output is correct
2 Correct 51 ms 820 KB Output is correct
3 Correct 1 ms 260 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 51 ms 852 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 436 KB Output is correct
2 Correct 60 ms 872 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 51 ms 816 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 308 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 596 KB Output is correct
2 Correct 59 ms 868 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 24 ms 596 KB Output is correct
6 Correct 1 ms 340 KB Output is correct