Submission #588282

#	Time	Username	Problem	Language	Result	Execution time	Memory
588282		tht2005	Burza (COCI16_burza)	C++17	160 / 160	25 ms	3068 KiB

burza

#include <bits/stdc++.h>

using namespace std;

int rd() {
    bool neg = 0; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if(c == '-') neg = !neg;
    int n = 0; while('0' <= c && c <= '9') n = (n << 3) + (n << 1) + c - '0', c = getchar();
    return neg ? -n : n;
}
void wr(int n) {
    static char o[11];
    if(n < 0) putchar('-'), n = -n;
    int i = 0; do o[i++] = n % 10 + '0'; while(n /= 10);
    while(i--) putchar(o[i]);
}

const int N = 402;
const int K = 20;
int n, k, t = 0, tin[N], tout[N], d[N];
bool f[N][1 << K];
vector<int> aj[N], ver[N];

void dfs(int v, int p) {
    if(d[v] == k) {
        tin[v] = t;
        tout[v] = ++t;
    }
    else {
        tin[v] = t;
        for(int u : aj[v]) {
            if(u == p) {
                continue;
            }
            d[u] = d[v] + 1;
            dfs(u, v);
        }
        tout[v] = t;
    }
}

int main() {
    n = rd();
    k = rd();
    if(k * k >= n) {
        puts("DA");
        return 0;
    }
    for(int i = 1, u, v; i < n; ++i) {
        u = rd();
        v = rd();
        aj[u].push_back(v);
        aj[v].push_back(u);
    }
    d[1] = 0;
    dfs(1, 0);
    for(int i = 2; i <= n; ++i) {
    	if(tin[i] != tout[i]) {
    		ver[tin[i]].push_back(i);
    	}
    }
    f[0][0] = 1;
    for(int i = 0; i < t; ++i) {
        for(int j = 1 << k; j--; ) {
            if(f[i][j]) {
                for(int v : ver[i]) {
                    if(j >> (d[v] - 1) & 1) {
                        continue;
                    }
                    f[tout[v]][j | (1 << (d[v] - 1))] = 1;
                }
            }
        }
    }
    for(int i = 1 << k; i--; ) {
        if(f[t][i]) {
            puts("DA");
            return 0;
        }
    }
    puts("NE");
    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