Submission #550968

#	Time	Username	Problem	Language	Result	Execution time	Memory
550968		Alexandruabcde	Burza (COCI16_burza)	C++14	160 / 160	64 ms	3312 KiB

burza

#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 / 16
• Subtask 2: 16 / 16
• Subtask 3: 16 / 16
• Subtask 4: 16 / 16
• Subtask 5: 16 / 16
• Subtask 6: 16 / 16
• Subtask 7: 16 / 16
• Subtask 8: 16 / 16
• Subtask 9: 16 / 16
• Subtask 10: 16 / 16