제출 #1220403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220403		vanea	Burza (COCI16_burza)	C++20	160 / 160	31 ms	840 KiB

burza

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int mxN = 4e2+10;

vector<int> adj[mxN];

int k;
map<int, int> lost;
vector<int> depth_nodes[mxN];
vector<int> cutoff_cover[mxN];
array<int, 2> intervals[mxN];

void dfs(int node, int p, int dep) {
    depth_nodes[dep].push_back(node);
    if(dep == k) {
        lost[node] = lost.size();
        cutoff_cover[node] = {node};
        return ;
    }
    for(auto it : adj[node]) {
        if(it == p) continue;
        dfs(it, node, dep+1);
        cutoff_cover[node].insert(cutoff_cover[node].end(),
                                  cutoff_cover[it].begin(), cutoff_cover[it].end());
    }

}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n >> k;
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    if(k * k >= n) {
        cout << "DA";
        return 0;
    }
    dfs(0, 0, 0);
    for(int i = 0; i < n; i++) {
        vector<int> &cc = cutoff_cover[i];
        if(cutoff_cover[i].empty()) intervals[i] = {-1, -1};
        else intervals[i] = {lost[cc.front()]+1, lost[cc.back()]+1};
    }
    vector<int> max_cover(1 << k);
    max_cover[0] = 0;
    for(int mask = 1; mask < (1 << k); mask++) {
        int &curr = max_cover[mask];
        for(int dep = 0; dep < k; dep++) {
            if(mask & (1 << dep)) {
                int prv = max_cover[mask ^ (1 << dep)];
                for(auto it : depth_nodes[dep+1]) {
                    if(intervals[it][0] <= prv+1) {
                        curr = max(curr, intervals[it][1]);
                    }
                }
            }
            if(max_cover[mask] == lost.size()) {
                cout << "DA";
                return 0;
            }
        }
    }
    cout << "NE";
    return 0;
}

• 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