oj.uz

Submission #729915

# Submission time Handle Problem Language Result Execution time Memory
729915 2023-04-24T20:22:00 Z PanosPask Burza (COCI16_burza) C++14
160 / 160
 64 ms 872 KB 
#include <bits/stdc++.h>
#define pb push_back
#define CHECK_BIT(val, pos) (val & (1<<pos))

using namespace std;

typedef pair<int, int> ii;

int n, k;
vector<vector<int>> adj_list;
vector<vector<int>> trimlist;
vector<int> subheight;
vector<int> p;
vector<int> depth;
vector<int> trimnum;
vector<ii> leafs;
int leafsize;
vector<vector<int>> depthnodes;
int trimcount = 0;
vector<int> dp;
int tot_leafs = 0;

void dfs(int node, int par, int d)
{
    depth[node] = subheight[node] = d;
    if (depth[node] == k) {
        leafs[node].first = leafs[node].second = ++tot_leafs;
        depthnodes[d].pb(node);
        return;
    }
    for (auto kid : adj_list[node])
        if (kid != par) {
            dfs(kid, node, d + 1);
            subheight[node] = max(subheight[node], subheight[kid]);
            leafs[node].first = min(leafs[node].first, leafs[kid].first);
            leafs[node].second = max(leafs[node].second, leafs[kid].second);
        }

    if (subheight[node] == k)
        depthnodes[d].push_back(node);
}

int main(void)
{
    scanf("%d %d", &n, &k);
    if (k * k > n) {
        printf("DA\n");
        return 0;
    }

    adj_list.resize(n);
    subheight.resize(n);
    depth.resize(n);
    leafs.assign(n, make_pair(INT_MAX, INT_MIN));
    depthnodes.resize(k+1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        adj_list[a].pb(b);
        adj_list[b].pb(a);
    }

    dfs(0, -1, 0);

    dp.resize(1<<k);
    dp[0] = 0;
    for (int s = 0; s < (1<<k); s++) {
        if (dp[s] == tot_leafs) {
            printf("DA\n");
            return 0;
        }
        for (int d = 0; d < k; d++)
            if (!CHECK_BIT(s, d)) {
                int prv_max = dp[s];
                for (auto node : depthnodes[d+1]) {
                    if (leafs[node].first <= prv_max + 1)
                        dp[s | (1<<d)] = max(dp[s | (1<<d)], leafs[node].second);
                }
            }
    }


    printf("NE\n");
    return 0;
}

Compilation message

burza.cpp: In function 'int main()':
burza.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
burza.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 340 KB Output is correct
2 Correct 56 ms 852 KB Output is correct
3 Correct 1 ms 228 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 852 KB Output is correct
2 Correct 46 ms 852 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 64 ms 852 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 45 ms 852 KB Output is correct
2 Correct 52 ms 852 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 212 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 13 ms 432 KB Output is correct
2 Correct 50 ms 852 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 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 852 KB Output is correct
2 Correct 46 ms 852 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 840 KB Output is correct
2 Correct 46 ms 852 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 852 KB Output is correct
2 Correct 48 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 47 ms 852 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 476 KB Output is correct
2 Correct 51 ms 840 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 304 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 57 ms 872 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 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 552 KB Output is correct
2 Correct 62 ms 864 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 600 KB Output is correct
6 Correct 0 ms 212 KB Output is correct