oj.uz

Submission #948866

# Submission time Handle Problem Language Result Execution time Memory
948866 2024-03-18T15:40:35 Z TrendBattles Burza (COCI16_burza) C++14
160 / 160
 33 ms 2144 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;
    depth[1] = -1;
    auto DFS = [&] (auto DFS, int u) {
        if (depth[u] == k - 1) {
            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) >> 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 2 ms 600 KB Output is correct
2 Correct 17 ms 2080 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 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 26 ms 1884 KB Output is correct
2 Correct 16 ms 1848 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 22 ms 1628 KB Output is correct
6 Correct 1 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1628 KB Output is correct
2 Correct 19 ms 1624 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 860 KB Output is correct
2 Correct 26 ms 2144 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1684 KB Output is correct
2 Correct 20 ms 1628 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 1 ms 344 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1964 KB Output is correct
2 Correct 26 ms 1880 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1916 KB Output is correct
2 Correct 19 ms 1628 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 26 ms 1628 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 712 KB Output is correct
2 Correct 18 ms 1884 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Correct 0 ms 456 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 600 KB Output is correct
2 Correct 33 ms 1884 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 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 860 KB Output is correct
2 Correct 23 ms 1884 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 11 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct