제출 #1131150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131150		henrlly	Burza (COCI16_burza)	C++20	160 / 160	83 ms	992 KiB

burza

// time-limit: 3000
#include <bits/stdc++.h>
#include <functional>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

#define ll long long

using vll = vector<ll>;
using vvll = vector<vector<ll> >;
using mpll = map<pair<ll, ll>, ll>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using pi = pair<int, int>;

void setIO(string name = "") {
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

void solve() {
    return;
}
unordered_map<int, vi> m;
unordered_map<int, vi> depths;
vector<pair<int,int> > ints; // intervals that each node covers
int bi = 0;
int k = 0;

pair<int,int> mergep(pair<int,int> &p1, pair<int,int> &p2) {
    if (p1.first == 0 && p1.second == 0) return p2;
    if (p2.first == 0 && p2.second == 0) return p1;
    return make_pair(min(p1.first, p2.first), max(p1.second, p2.second));
}

void dfs(int x, int prev, int depth) {
    depths[depth].push_back(x);
    if (depth == k) {
        bi++;
        ints[x] = make_pair(bi,bi);
        return;
    }

    for (auto &e: m[x]) {
        if (e != prev) {
            dfs(e, x, depth+1);
            ints[x] = mergep(ints[x], ints[e]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // setIO("test");

    // if k^2 >= n, then game can end.
    // at step i, delete a node at depth i
    // if we cut off largest subtree at every step,
    // tr is number of valid nodes with depth r+1
    // nr is the number of valid nodes at step r
    // nr+1 <= nr - nr/tr - (tr - 1)
    // nr/tr is the largest subtree
    // nodes with depth r are also removed
    // at 1 node at depth r from that largest subtree that was removed
    // to avoid double count
    //

    int n;
    cin >> n >> k;
    ints.resize(n+1);
    for (int i = 0; i < n-1; i++) {
        int a, b;
        cin >> a >> b;
        m[a].push_back(b);
        m[b].push_back(a);
    }

    if (k * k >= n) {
        cout << "DA" << endl;
        return 0;
    }

    // dfs to leaf nodes (when depth == k)
    // assign new leaf nodes a new index,
    // leaf node's own interval is [index, index]
    // then update intervals of parents
    // store node depths too
    //
    // bitwise dp[s] = n,
    // s&(1<<i) means a node at depth i+1 is in subset
    // where subset can cover leaves 1...n
    // if s&(1<<i) s^(1<<i) and merge with interval of node j, for all node j at depth i

    dfs(1, -1, 0);
    vi dp(1<<k);
    for (int s = 1; s < 1<<k; s++) {
        for (int i = 0; i < k; i++) {
            if (s&(1<<i)) {
                dp[s] = max(dp[s], dp[s^(1<<i)]);
                for (auto &e: depths[i+1]) {
                    if (ints[e].first <= dp[s^(1<<i)]+1) dp[s] = max(dp[s], ints[e].second);
                }
            }
        }
    }

    cout << (dp[(1<<k)-1] == bi ? "DA" : "NE") << endl;

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

burza.cpp: In function 'void setIO(std::string)':
burza.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
burza.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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