oj.uz

Submission #550968

# Submission time Handle Problem Language Result Execution time Memory
550968 2022-04-19T14:32:57 Z Alexandruabcde Burza (COCI16_burza) C++14
160 / 160
 64 ms 3312 KB 
#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 405;
constexpr int KMAX = 20;

int N, K;
vector <int> G[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> K;

    for (int i = 1; i < N; ++ i ) {
        int a, b;
        cin >> a >> b;

        G[a].push_back(b);
        G[b].push_back(a);
    }
}

int Level[NMAX];
int Start[NMAX], Finish[NMAX];
int vf;

void Dfs (int Node, int dad) {
    Level[Node] = Level[dad] + 1;

    if (Level[Node] == K-1) {
        Start[Node] = vf;
        vf ++;
        Finish[Node] = vf;
        return;
    }

    Start[Node] = vf;

    for (auto it : G[Node]) {
        if (it == dad) continue;

        Dfs(it, Node);
    }

    Finish[Node] = vf;
}

bool dp[NMAX][(1<<KMAX)];
vector <int> Interval[NMAX];

void Solve () {
    if (K * K >= N) {
        cout << "DA\n";
        return;
    }

    Level[0] = -2;
    Dfs(1, 0);

    for (int i = 2; i <= N; ++ i )
        Interval[Start[i]].push_back(i);

    dp[0][0] = true;

    for (int i = 0; i < vf; ++ i ) {
        for (int mask = 0; mask < (1<<K); ++ mask ) {
            if (!dp[i][mask]) continue;

            for (auto it : Interval[i]) {
                int who = Level[it];
                if ((mask&(1<<who))) continue;

                dp[Finish[it]][mask^(1<<who)] = true;
            }
        }
    }

    bool ans = false;
    for (int mask = 0; mask < (1<<K); ++ mask )
        ans |= dp[vf][mask];

    cout << (ans == true ? "DA" : "NE") << '\n';
}

int main () {
    Read();
    Solve();

    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 980 KB Output is correct
2 Correct 40 ms 2580 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 2640 KB Output is correct
2 Correct 41 ms 2536 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 64 ms 3020 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 2760 KB Output is correct
2 Correct 47 ms 2540 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1364 KB Output is correct
2 Correct 62 ms 3312 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 468 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2292 KB Output is correct
2 Correct 49 ms 2908 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 860 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2644 KB Output is correct
2 Correct 48 ms 2764 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 980 KB Output is correct
6 Correct 1 ms 724 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3044 KB Output is correct
2 Correct 50 ms 2764 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 59 ms 3116 KB Output is correct
6 Correct 1 ms 864 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1236 KB Output is correct
2 Correct 51 ms 2628 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 980 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB Output is correct
2 Correct 61 ms 3112 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 980 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1620 KB Output is correct
2 Correct 58 ms 3068 KB Output is correct
3 Correct 1 ms 356 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 23 ms 1604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct