Submission #1196061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196061		KALARRY	Burza (COCI16_burza)	C++20	160 / 160	59 ms	988 KiB

burza

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int N,K,depth[405],score[405],first_leaf[405],counter,dp[(1<<20)];
vector<int> nodes_per_depth[405];
vector<int> adj[405];

void dfs1(int v,int p)
{
    first_leaf[v] = N+1;
    for(auto u : adj[v])
        if(u != p)
        {
            depth[u] = depth[v] + 1;
            nodes_per_depth[depth[u]].push_back(u);
            dfs1(u,v);
            score[v] += score[u];
            first_leaf[v] = min(first_leaf[v],first_leaf[u]);
        }
    if(depth[v]==K-1)
    {
        score[v]++;
        first_leaf[v] = ++counter;
    }
}

int main()
{
    scanf("%d%d",&N,&K);
    for(int a,b,i = 1 ; i < N ; i++)
    {
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    depth[1] = -1; //to push others for zero indexing
    dfs1(1,1);
    if(K >= 21)
        printf("DA\n");
    else
    {
        for(int mask = 1 ; mask < (1<<K) ; mask++)
        {
            for(int j = 0 ; j <= K-1 ; j++)
                if(mask & (1<<j))
                {
                    for(auto x : nodes_per_depth[j])
                    {
                        int l = first_leaf[x];
                        int r = first_leaf[x] + score[x] - 1;
                        if(score[x]==0)
                            continue;
                        int new_mask = mask ^ (1<<j);
                        dp[mask] = max(dp[mask],dp[new_mask]);
                        if(l <= dp[new_mask] + 1)
                            dp[mask] = max(dp[mask],r);
                    }
                }
        }
        if(dp[(1<<K) - 1] >= score[1])
            printf("DA\n");
        else
            printf("NE\n");
    }
    return 0;
}

Compilation message (stderr)

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

• 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