Submission #1265545

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265545		longgggg	Burza (COCI16_burza)	C++17	160 / 160	31 ms	6216 KiB

burza

#include <bits/stdc++.h>
using namespace std;
//====== BITWISE ======//
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ON(x, i) ((x) | MASK(i))
#define OFF(x, i) ((x) & ~MASK(i))
#define LASTBIT(mask) ((mask) & -(mask))
#define SUBMASK(sub, mask) for (int sub = (mask); sub >= 1; sub = (sub - 1) & (mask))
//====== OTHER ======//
#define fi first
#define se second
#define ll long long
#define endl '\n'
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define mod(x, k) ((((x) % (k)) + (k)) % (k))
#define compress(c) sort(all(c)); c.erase(unique(all(c)), c.end());
#define Longgggg ios_base::sync_with_stdio(0); cin.tie(0);
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
//====== FILE ======//
#define IN "A.in"
#define OUT "A.out"
#define DEBUG "debug.out"
//==================//

const int INF = (int) 1e9+5;
const ll LINF = (ll) 1e18;
const ll MOD = (ll) 1e9+7;
const int mxN = (int) 1e5+5;

int n, k;
vector <int> adj[mxN], nodesAtDepth[mxN];
vector <pair <int, int>> coveredInterval(mxN, {-1, -1});
int leafCnt = 0;

// Dfs de set doan duoc phu boi la co do sau k
void dfs(int u, int pre, int d) {
    if (d > k) return; // Khong can quan tam nhung nut sau hon (max dinh thua)
    nodesAtDepth[d].push_back(u);

    if (d == k) {
        coveredInterval[u] = {leafCnt, leafCnt};
        ++leafCnt;
        return;
    }
    // d < k
    int L = INF, R = -INF;
    for (auto &v : adj[u]) {
        if (v == pre) continue;
        dfs(v, u, d+1);

        pair <int, int> seg = coveredInterval[v];
        if (seg.fi != -1) {
            L = min(L, seg.fi);
            R = max(R, seg.se);
        }
    }
    if (R != -INF) coveredInterval[u] = {L, R};
}

void solve() {
    cin >> n >> k;
    FOR(i, 1, n-1) {
        int u, v; cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if (1LL * k * k >= n) {
        cout << "DA\n";
        return;
    }

    dfs(0, -1, 0);

    vector <int> dp(MASK(k), -1);
    // dp[mask]: range [0...R] is covered
    dp[0] = 0;

    FOR(mask, 1, MASK(k)-1) {
        int bestR = -1;
        FOR(i, 0, k-1) if (BIT(mask, i)) {
            int lst = OFF(mask, i);
            if (dp[lst] == -1) continue;

            for (auto &u : nodesAtDepth[i+1]) {
                pair <int, int> seg = coveredInterval[u];
                if (seg.fi == -1) continue;
                if (seg.fi <= dp[lst]) bestR = max(bestR, max(dp[lst], seg.se+1));
            }
        }

        dp[mask] = bestR;
        if (dp[mask] == leafCnt) {
            cout << "DA\n";
            return;
        }
    }

    cout << "NE\n";
}

signed main() {
    if (fopen(IN, "r")) {
        freopen(IN, "r", stdin);
        freopen(OUT, "w", stdout);
        freopen(DEBUG, "w", stderr);
    }
    Longgggg

    ll t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen(IN, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
burza.cpp:109:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         freopen(OUT, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
burza.cpp:110:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |         freopen(DEBUG, "w", stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

• 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