oj.uz

Submission #407394

# Submission time Handle Problem Language Result Execution time Memory
407394 2021-05-18T21:18:22 Z CrouchingDragon Burza (COCI16_burza) C++17
160 / 160
 194 ms 6768 KB 
#include "bits/stdc++.h"

using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define all(x) begin(x), end(x)

using ll = long long;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, K;
    cin >> N >> K;

    if (K * K > N) {
        cout << "DA" << endl;
        exit(0);
    }

    vector<vector<int>> E(N);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        E[u].push_back(v), E[v].push_back(u);
    }

    vector<int> h(N), L(N), R(N), V;
    int timer = 0;
    auto dfs = [&](auto&& self, int u, int p) -> void {
        L[u] = timer;
        if (h[u] < K) {
            for (auto v : E[u]) {
                if (v != p) {
                    h[v] = h[u] + 1;
                    self(self, v, u);
                }
            }
        }
        R[u] = timer++;
        V.push_back(u);
    };
    h[0] = -1;
    dfs(dfs, 0, -1);

    vector<vector<bool>> memo(N);
    vector<bool> dp(1 << K), dpnxt(1 << K);
    dp[0] = true;

    V.pop_back();
    for (auto u : V) {
        if (L[u] > 0) {
            for (int mask = 0; mask < (1 << K); ++mask) {
                if (memo[L[u] - 1][mask] && (mask >> h[u] & 1) == 0) {
                    dpnxt[mask | 1 << h[u]] = true;
                }
            }
        }
        else dpnxt[1 << h[u]] = true;

        if (h[u] < K - 1) {
            for (int mask = 0; mask < (1 << K); ++mask) {
                dpnxt[mask] = dpnxt[mask] || dp[mask];
            }
        }
        fill(all(dp), false), swap(dp, dpnxt);
        memo[R[u]] = dp;
    }

    string ans = count(all(dp), true) ? "DA" : "NE";
    cout << ans << endl;

    exit(0);
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 972 KB Output is correct
2 Correct 188 ms 6740 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 6440 KB Output is correct
2 Correct 183 ms 6480 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 194 ms 6652 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 6476 KB Output is correct
2 Correct 184 ms 6468 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1740 KB Output is correct
2 Correct 191 ms 6768 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 6264 KB Output is correct
2 Correct 190 ms 6472 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 6460 KB Output is correct
2 Correct 190 ms 6284 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 6500 KB Output is correct
2 Correct 182 ms 6340 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 191 ms 6464 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1584 KB Output is correct
2 Correct 187 ms 6572 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 372 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 900 KB Output is correct
2 Correct 191 ms 6640 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 2912 KB Output is correct
2 Correct 189 ms 6660 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 83 ms 2976 KB Output is correct
6 Correct 1 ms 332 KB Output is correct