Submission #1097416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097416		tinnhiemnn	Burza (COCI16_burza)	C++17	160 / 160	31 ms	988 KiB

burza

#include <bits/stdc++.h>
using namespace std;
#define file "file"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
const int N=405;
int n,k,dp[1<<20],l[N],r[N],Time;
vector<int> E[N],depth[22];

void dfs(int u, int pa, int d)
{
    depth[d].pb(u);

    if (d==k)
    {
        Time++;
        l[u]=Time; r[u]=Time;
        return;
    }

    l[u]=INT_MAX; r[u]=0;
    for (int v : E[u]) if (v!=pa)
    {
        dfs(v, u, d+1);
        l[u]=min(l[u], l[v]); r[u]=max(r[u], r[v]);
    }
}
int main()
{
    //freopen(file".inp", "r", stdin);
    //freopen(file".out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin>>n>>k;
    if (k*k > n) {cout<<"DA"; return 0;}

    for (int i=1;i<n;i++)
    {
        int u,v; cin>>u>>v; E[u].pb(v); E[v].pb(u);
    }

    dfs(1, 0, 0);
    dp[0]=0;
    for (int mask=1; mask < (1<<k); mask++)
    {
        for (int i=0;i<k;i++) if ((mask>>i) & 1)
        {
            int cur = mask ^ (1<<i);
            for (int u : depth[i+1])
                if (l[u] <= dp[cur]+1) dp[mask]=max(dp[mask], r[u]);
        }
        if (dp[mask] == Time) {cout<<"DA"; return 0;}
    }
    cout<<"NE";

}

• 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