Submission #1249390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249390		nrg_studio	Burza (COCI16_burza)	C++20	160 / 160	287 ms	2516 KiB

burza

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int N = 400, K = 19;
vec<int> adj[N];
int dep[N] = {-1};
pair<int,int> range[N];
int dp[1<<K] = {0};
int k;
int m = 0;

void dfs(int cur=0, int par=-1) {
    range[cur] = {INT_MAX,INT_MIN};
    if (dep[cur]==k-1) {
        m++;
        range[cur] = {m,m};
        return;
    }
    for (int x : adj[cur]) {
        if (x!=par) {
            dep[x] = dep[cur]+1;
            dfs(x,cur);
            chmin(range[cur].f,range[x].f);
            chmax(range[cur].s,range[x].s);
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n >> k;
    k = min(19,k);
    for (int i=0;i<n-1;i++) {
        int a, b; cin >> a >> b;
        adj[--a].pb(--b);
        adj[b].pb(a);
    }
    dfs();
    //F0R(i,n) {cout<<range[i].f<<' '<<range[i].s<<'\n';}
    for (int i=0;i<(1<<k);i++) {
        for (int j=1;j<n;j++) {
            if ((1<<dep[j])&i) {continue;}
            if (range[j].f<=dp[i]+1) {
                chmax(dp[i|(1<<dep[j])],max(range[j].s,dp[i]));
            }
        }
    }
    cout << (dp[(1<<k)-1]==m ? "DA" : "NE") << '\n';
}

• 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