oj.uz

Submission #948842

# Submission time Handle Problem Language Result Execution time Memory
948842 2024-03-18T15:26:45 Z TrendBattles Burza (COCI16_burza) C++14
160 / 160
 35 ms 3684 KB 
//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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 16 ms 3684 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3264 KB Output is correct
2 Correct 16 ms 3164 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 25 ms 3160 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3160 KB Output is correct
2 Correct 20 ms 3164 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1548 KB Output is correct
2 Correct 31 ms 3676 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 456 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2864 KB Output is correct
2 Correct 24 ms 2908 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3420 KB Output is correct
2 Correct 28 ms 2904 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3416 KB Output is correct
2 Correct 20 ms 3016 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Correct 26 ms 2908 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1116 KB Output is correct
2 Correct 18 ms 3524 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 604 KB Output is correct
2 Correct 35 ms 3420 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1480 KB Output is correct
2 Correct 27 ms 3416 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 11 ms 1628 KB Output is correct
6 Correct 1 ms 344 KB Output is correct