oj.uz

답안 #588282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
588282 2022-07-03T01:52:02 Z tht2005 Burza (COCI16_burza) C++17
160 / 160
 25 ms 3068 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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