Submission #918463

#	Time	Username	Problem	Language	Result	Execution time	Memory
918463		vjudge1	Burza (COCI16_burza)	C++11	160 / 160	50 ms	93020 KiB

burza

/*
6 2
1 2
2 3
3 4
1 5
5 6

Daniel cannot see the coin-must block the coin before it moves k times
 - Block all places of depth 1, then 2, ...?
*/
#include <iostream>
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define pii pair<int, int>
#define pil pair<int, ll>
const int maxn = 403;
const int maxk = 20;
int n; int k;
vi edg[maxn]; vi by_dpth[maxn];
bool dp[maxn][(1<<maxk)];
int dpth[maxn]; int plc = 0;
pii rg[maxn]; //range covered by node, try to cover entire tree

void inorder(int c, int p, int d){ //cover all leaves from l...r, ignore leaves past depth k
    dpth[c] = d;
    if(d >= k-1){
        //cout << "set " << plc << " at node " << c << endl;
        rg[c].first = plc; rg[c].second = ++plc;
        return;
    }
    rg[c].first = plc;
    for(int e : edg[c]){
        if(e == p) continue;
        inorder(e, c, d+1);
    }
    rg[c].second = plc; //just stores progression of leaf nodes
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    for(int a = 0; a < n-1; a++){
        int f; int s; cin >> f >> s;
        f--; s--;
        edg[f].push_back(s); edg[s].push_back(f);
    }
    if(k*k >= n) cout << "DA\n";
    else{
        //bitmask dp!!!
        inorder(0, -1, -1);
        for(int a = 1; a < n; a++){
            by_dpth[rg[a].first].push_back(a);
            //cout << "range of " << a << " " << rg[a].first << " to " << rg[a].second << endl;
        }
        dp[0][0] = true;
        for(int leaf = 0; leaf < plc; leaf++){
            for(int msk = 0; msk < (1 << k); msk++){
                if(!dp[leaf][msk]) continue;
                for(int e : by_dpth[leaf]){
                    if((msk & (1 << dpth[e])) <= 0){
                        dp[rg[e].second][(msk | (1 << dpth[e]))] = true;
                    }
                }
            }
        }
        bool works = false;
        for(int msk = 0; msk < (1<<k); msk++){
            //cout << plc << " dp " << dp[plc][msk] << endl;
            works |= dp[plc][msk];
        }
        if(works) cout << "DA\n";
        else cout << "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