Submission #918451

#	Time	Username	Problem	Language	Result	Execution time	Memory
918451		PikaChu999	Burza (COCI16_burza)	C++14	0 / 160	7 ms	4700 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];
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){
        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 >= 20 || k*k >= n) cout << "DA\n";
    else{
        //bitmask dp!!!
        inorder(0, -1, 0);
        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 : edg[leaf]){
                    if((msk & (1 << dpth[e])) <= 0 && leaf >= rg[e].first){
                        dp[max(rg[e].second, leaf)][(msk | (1 << dpth[e]))] = true;
                    }
                }
            }
        }
        bool works = false;
        for(int msk = 0; msk < (1<<k); msk++){
            works |= dp[plc][msk];
        }
        if(works) cout << "DA\n";
        else cout << "NE\n";
    }
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16