Submission #766447

#	Time	Username	Problem	Language	Result	Execution time	Memory
766447		vjudge1	Burza (COCI16_burza)	C++17	160 / 160	40 ms	848 KiB

burza

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cstdlib>
#include <bitset>
#include <deque>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 405;
vector<int> g[maxn];
int dp[1 << 20];
int n, k;
int cnt, lf[maxn], rf[maxn];
vector<int> depth[maxn];
void dfs(int u, int fa, int dep) {
    depth[dep].push_back(u);
    if (dep == k) {
        lf[u] = rf[u] = ++cnt;
        return;
    }
    lf[u] = inf, rf[u] = -inf;
    for (int v : g[u]) {
        if (v == fa) continue;
        dfs(v, u, dep + 1);
        lf[u] = min(lf[u], lf[v]);
        rf[u] = max(rf[u], rf[v]);
    }
}
int main() {
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    if (n <= k * k) {
        cout << "DA" << endl;
        return 0;
    }
    dfs(1, 0, 0);
    for (int s = 1; s < (1 << k); s++) {
        for (int i = 0; i < k; i++) {
            if (~s & (1 << i)) continue;
            int pre = dp[s ^ (1 << i)];
            for (int u : depth[i + 1]) {
                if (lf[u] <= pre + 1) {
                    dp[s] = max(dp[s], rf[u]);
                }
            }
        }
        if (dp[s] >= cnt) {
            cout << "DA" << endl;
            return 0;
        }
    }
    cout << "NE" << endl;
    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