Submission #948842

#	Time	Username	Problem	Language	Result	Execution time	Memory
948842		TrendBattles	Burza (COCI16_burza)	C++14	160 / 160	35 ms	3684 KiB

burza

//https://oj.uz/problem/view/COCI16_burza

#include <bits/stdc++.h>
using namespace std;
using lli = int64_t;

#define INFILE "burza.inp"
#define OUTFILE "burza.out"
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    if (fopen(INFILE, "r")) {
        freopen(INFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }
    int n, k; cin >> n >> k;

    if (k * k >= n) {
        cout << "DA\n"; return 0;
    }
    vector <vector <int>> graph(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector <int> leaves_L(n + 1, -1), leaves_R(n + 1, -1), depth(n + 1), parent(n + 1);

    int vir_l = 0;
    auto DFS = [&] (auto DFS, int u) {
        if (depth[u] == k) {
            leaves_L[u] = vir_l++;
            leaves_R[u] = vir_l;
            return;
        }

        leaves_L[u] = vir_l;
        for (int v : graph[u]) {
            if (v == parent[u]) continue;
            parent[v] = u;
            depth[v] = depth[u] + 1;

            DFS(DFS, v);
        }

        leaves_R[u] = vir_l;
    };
    DFS(DFS, 1);

    vector <vector <int>> list_leaves(vir_l + 5);
    for (int i = 2; i <= n; ++i) {
        if (leaves_L[i] == -1) continue;
        list_leaves[leaves_L[i]].push_back(i);
    }
    
    //for (int i = 1; i <= n; ++i) cerr << leaves_L[i] << ' ' << leaves_R[i] << '\n';
    const int limit = ((1 << (k + 1)) >> 6) + 5;

    vector <vector <lli>> dp(vir_l + 5, vector <lli> (limit));
    dp[0][0] = 1;

    for (int T = 0; T < vir_l; ++T) {
        for (int mask_block = 0; mask_block < limit; ++mask_block) {
            for (lli x = dp[T][mask_block]; x; x -= x & -x) {
                int mask = (mask_block << 6) | __builtin_ctzll(x);

                //cerr << "DEBUG: "<< T << ' ' << mask << '\n';
                for (int nxt : list_leaves[T]) {
                    if (mask >> depth[nxt] & 1) continue;

                    //cerr << "NXT: " << nxt << '\n';
                    int nxt_mask = mask | (1 << depth[nxt]);

                    dp[leaves_R[nxt]][nxt_mask >> 6] |= 1LL << (nxt_mask & 63);
                }
            }
        }
    }

    int exist = false;
    for (int i = 0; i < limit; ++i) {
        if (dp[vir_l][i]) {
            exist = true; break;
        }
    }
    cout << (exist ? "DA" : "NE");
    return 0;
}

Compilation message (stderr)

burza.cpp: In function 'int main()':
burza.cpp:12:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         freopen(INFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
burza.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen(OUTFILE, "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