Submission #735313

#	Time	Username	Problem	Language	Result	Execution time	Memory
735313		Nhoksocqt1	Burza (COCI16_burza)	C++17	160 / 160	59 ms	1000 KiB

burza

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

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
    inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
    inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 404;

vector<int> adj[MAXN], B[MAXN];
ii leafs[MAXN];
int dp[1 << 20];
int depth[MAXN], pa[MAXN], numNode, numTurn;

int dfs(int u, int p) {
    if(depth[u] == numTurn) {
        leafs[u].fi = leafs[u].se = ++leafs[0].fi;
        B[depth[u]].push_back(u);
        return depth[u];
    }

    leafs[u].fi = 1e9, leafs[u].se = 0;
    int maxDepth(depth[u]);
    for (int it = 0; it < sz(adj[u]); ++it) {
        int v(adj[u][it]);
        if(v != p) {
            pa[v] = u;
            depth[v] = 1 + depth[u];
            maxDepth = max(maxDepth, dfs(v, u));
            leafs[u].fi = min(leafs[u].fi, leafs[v].fi);
            leafs[u].se = max(leafs[u].se, leafs[v].se);
        }
    }

    if(maxDepth == numTurn)
        B[depth[u]].push_back(u);

    return maxDepth;
}

void process() {
    cin >> numNode >> numTurn;
    for (int i = 1; i < numNode; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if(numTurn * numTurn > numNode) {
        cout << "DA\n";
        return;
    }

    dfs(1, -1);
    for (int mask = 0; mask < (1 << numTurn); ++mask) {
        for (int i1 = ((1 << numTurn) - 1) ^ mask; i1 > 0; i1 ^= i1 & -i1) {
            int i = __builtin_ctz(i1 & -i1);
            for (int it = 0; it < sz(B[i + 1]); ++it) {
                int u(B[i + 1][it]);
                if(leafs[u].fi <= dp[mask] + 1) {
                    dp[mask | (1 << i)] = max(dp[mask | (1 << i)], leafs[u].se);
                }
            }
        }
    }

    if(dp[(1 << numTurn) - 1] == leafs[1].se) {
        cout << "DA\n";
    } else {
        cout << "NE\n";
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    process();
    return 0;
}

• 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