oj.uz

Submission #766447

# Submission time Handle Problem Language Result Execution time Memory
766447 2023-06-25T16:28:34 Z vjudge1 Burza (COCI16_burza) C++17
160 / 160
 40 ms 848 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 38 ms 812 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 752 KB Output is correct
2 Correct 37 ms 772 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 38 ms 844 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 788 KB Output is correct
2 Correct 40 ms 848 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 412 KB Output is correct
2 Correct 38 ms 820 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 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 35 ms 748 KB Output is correct
2 Correct 37 ms 800 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 744 KB Output is correct
2 Correct 37 ms 784 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 844 KB Output is correct
2 Correct 37 ms 760 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 38 ms 752 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 464 KB Output is correct
2 Correct 37 ms 816 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 328 KB Output is correct
2 Correct 39 ms 804 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 580 KB Output is correct
2 Correct 37 ms 772 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 17 ms 604 KB Output is correct
6 Correct 1 ms 340 KB Output is correct