Submission #395565

#	Time	Username	Problem	Language	Result	Execution time	Memory
395565		iANikzad	Burza (COCI16_burza)	C++14	160 / 160	84 ms	10564 KiB

burza

#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
//#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 4e2 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int maxl = 20;
const int SQ = 400;

int n, k;

int dp[maxn][(1 << maxl)];
vector<int> vec[maxn];

vector<int> adj[maxn];

int h[maxn];
int st[maxn], en[maxn];
int timer;

void dfs(int v,int par = 0)
{
    if(h[v] == k - 1)
    {
        st[v] = timer++; en[v] = timer;
        return;
    }

    st[v] = timer;
    for(int u : adj[v])
    {
        if(u == par) continue;
        h[u] = h[v] + 1;
        dfs(u, v);
    }
    en[v] = timer;
}

int32_t main()
{
    FAST;

    cin >> n >> k;

    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;

        adj[u].pb(v), adj[v].pb(u);
    }

    if(n <= k * k) return cout << "DA\n", 0;

    h[1] = -1;
    dfs(1);

    for(int i = 2; i <= n; i++)
        vec[st[i]].pb(i);

    dp[0][0] = 1;
    for(int i = 0; i < timer; i++)
        for(int mask = 0; mask < (1 << k); mask++) if(dp[i][mask])
            for(int v : vec[i]) if(!(mask >> h[v] & 1))
                dp[en[v]][mask + (1 << h[v])] = 1;

    for(int mask = 0; mask < (1 << k); mask++) if(dp[timer][mask]) return cout << "DA\n", 0;
    cout << "NE\n";

    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