Submission #588282

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
588282	2022-07-03T01:52:02 Z	tht2005	Burza (COCI16_burza)	C++17	160 / 160	25 ms	3068 KB

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.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	852 KB	Output is correct
2	Correct	16 ms	2496 KB	Output is correct
3	Correct	1 ms	324 KB	Output is correct
4	Correct	0 ms	212 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	19 ms	2644 KB	Output is correct
2	Correct	16 ms	2404 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	23 ms	2828 KB	Output is correct
6	Correct	1 ms	980 KB	Output is correct

Subtask #3
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	2636 KB	Output is correct
2	Correct	17 ms	2420 KB	Output is correct
3	Correct	0 ms	328 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	844 KB	Output is correct
6	Correct	1 ms	452 KB	Output is correct

Subtask #4
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	1236 KB	Output is correct
2	Correct	25 ms	3068 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	836 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	2116 KB	Output is correct
2	Correct	19 ms	2772 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	328 KB	Output is correct
5	Correct	1 ms	980 KB	Output is correct
6	Correct	1 ms	852 KB	Output is correct

Subtask #6
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	2672 KB	Output is correct
2	Correct	18 ms	2644 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	852 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	22 ms	2736 KB	Output is correct
2	Correct	19 ms	2732 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	324 KB	Output is correct
5	Correct	18 ms	2900 KB	Output is correct
6	Correct	1 ms	852 KB	Output is correct

Subtask #8
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	1236 KB	Output is correct
2	Correct	19 ms	2632 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	324 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	2 ms	724 KB	Output is correct
2	Correct	22 ms	2808 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 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	9 ms	1620 KB	Output is correct
2	Correct	19 ms	2816 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	10 ms	1604 KB	Output is correct
6	Correct	1 ms	596 KB	Output is correct

Submission #588282

Compilation message