oj.uz

Submission #948848

# Submission time Handle Problem Language Result Execution time Memory
948848 2024-03-18T15:30:12 Z TrendBattles Burza (COCI16_burza) C++14
0 / 160
 2 ms 3676 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] = max(vir_l, 1);
        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 + 1]) {
                    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
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 2 ms 3160 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 2 ms 3164 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 2 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 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 2 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 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 1 ms 2920 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3164 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 2 ms 2904 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 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 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 2 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 Incorrect 1 ms 1372 KB Output isn't correct
6 Halted 0 ms 0 KB -