Submission #975345

#	Time	Username	Problem	Language	Result	Execution time	Memory
975345		u_suck_o	Burza (COCI16_burza)	C++17	160 / 160	32 ms	964 KiB

burza

#include <iostream>
#include <vector>
#define l first
#define r second
#include <climits>
using namespace std;

vector<pair<int,int>> intv(405, make_pair(INT_MAX,INT_MIN));
int range[1 << 20];
vector<int> nodesAtDepth[21];
vector<int> adj[405];
int leaf;
int N, K;
bool dfs(int node, int parent, int dep) {
    if (dep == K) {
        ++leaf;
        nodesAtDepth[dep].push_back(node);
        intv[node] = {leaf,leaf};
        return true;
    }
    bool valid = false;
    for (auto child: adj[node]) {
        if (child != parent) {
            if ( dfs(child, node, dep+1) ) {
                if (intv[child].l < intv[node].l) intv[node].l = intv[child].l;
                if (intv[child].r > intv[node].r) intv[node].r = intv[child].r;
                valid = true;
            }
        }
    }
    if (!valid) return false;
    nodesAtDepth[dep].push_back(node);
    return true;
}

int main() {
  
    std::cin >> N >> K;
    
    for (int e = 1; e <= N - 1; e++) {
        int n1, n2;
        cin >> n1 >> n2;
        adj[n1].push_back(n2);
        adj[n2].push_back(n1);
    }

    if (K * K >= N) {
        cout << "DA" << endl;
        return 0;
    }
    
    // find all leaf nodes
    dfs(1, -1, 0);

    range[0] = 0;
    for (int mask = 1; mask < (1 << K); mask++) {
        int curr = range[mask];
        // go through each possible previous masks
        for (int lastBit = 0; lastBit < K; lastBit++) {
            if ((mask & (1 << lastBit)) != 0) {
                int prev = range[mask & ~(1 << lastBit)];
                // find the best node at given depth
                for (int n : nodesAtDepth[lastBit + 1]) {
                    if (intv[n].first <= prev + 1) {
                        curr = std::max(curr, intv[n].second);
                        range[mask] = curr;
                    }
                }
            }
        }

        if (range[mask] == leaf) {
            cout << "DA" << endl;
            return 0;
        }
    }

    cout << "NE" << endl;
}

• 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