Submission #1217805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217805		sam230609	Burza (COCI16_burza)	C++20	0 / 160	220 ms	940 KiB

burza

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
vector<int> adj[401];
int dep[401],dp[1<<19],l[401],r[401],curr,n,k;
void dfs(int v, int p){
    if(dep[v]==k) {l[v]=r[v]=++curr; return; }
    for(int u:adj[v]){
        if(u==p) continue;
        dep[u]=dep[v]+1; dfs(u,v);
        l[v]=min(l[v],l[u]);
        r[v]=max(r[v],r[u]);
    }
}
int main(){
    cin >>n>>k;
    memset(l,INF,sizeof(l)); memset(r,0,sizeof(r));
    if(k>=20) {cout <<"NE\n"; return 0;}
    for(int i=1;i<n;i++){
        int a,b; cin >>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }dfs(1,-1);
    for(int mask=1;mask<(1<<k);mask++){
        dp[mask]=-INF;
        for(int i=1;i<=n;i++){
            if(!dep[i] || !(mask&(1<<(dep[i]-1)))) continue;
            if(dp[mask^(1<<(dep[i]-1))]+1>=l[i]) dp[mask]=max({dp[mask],r[i],dp[mask^(1<<(dep[i]-1))]});
        }
    }cout <<(dp[(1<<k)-1]==curr?"DA":"NE");
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16