Submission #96744

#	Time	Username	Problem	Language	Result	Execution time	Memory
96744		tieunhi	Burza (COCI16_burza)	C++14	160 / 160	60 ms	1144 KiB

burza

#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define ll long long
#define pill pair<int, ll>
#define PB push_back
#define mp make_pair
#define F first
#define S second
#define N 500
#define maxc 1000000007
#define mid (r + l)/2

using namespace std;

int n, k, dp[1 << 21], h[N], tt = 1, hmax[N], tin[N], tout[N], dd[N];
vector<int> a[N], v[N];

void stop() {cout <<"DA"; exit(0);}
bool bit(int x, int i) {return (x >> i) & 1;}
void inline MAX(int &A, int B) {A = max(A, B);}
void setup()
{
    cin >> n >> k;
    if (k >= 20) stop();

    FOR(i, 2, n)
    {
        int u, v; cin >> u >> v;
        a[u].PB(v);
        a[v].PB(u);
    }
}
void preDFS(int u, int p)
{
    hmax[u] = h[u];
    for (auto v : a[u])
    {
        if (v == p) continue;
        h[v] = h[u] + 1;
        preDFS(v, u);
        hmax[u] = max(hmax[u], hmax[v]);
    }
}
void DFS(int u, int p)
{
    tin[u] = tt;
    if (h[u] == k)
        tt++;
    for (auto v : a[u])
    {
        if (v == p || dd[v]) continue;
        DFS(v, u);
    }
    tout[u] = tt-1;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    //freopen("OUT.TXT", "w", stdout);
    setup();
    preDFS(1, -1);
    FOR(i, 1, n)
        if (h[i] > k || hmax[i] < k) dd[i] = 1;
        else v[h[i]].PB(i);
    if (hmax[1] < k) stop();
    DFS(1, -1);
    FOR(mask, 0, (1 << k)-1)
    {
        int cur = dp[mask];
        FOR(i, 1, k)
        {
            if (bit(mask, i-1)) continue;
            for (auto u : v[i])
            {
                if (tin[u] > cur+1) continue;
                MAX(dp[mask | (1 << (i-1))], max(dp[mask], tout[u]));
            }
        }
    }
    if (dp[(1 << k)-1] == tt-1) cout <<"DA";
    else 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