oj.uz

Submission #918462

# Submission time Handle Problem Language Result Execution time Memory
918462 2024-01-29T21:13:34 Z PikaChu999 Burza (COCI16_burza) C++11
160 / 160
 51 ms 93020 KB 
/*
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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 51804 KB Output is correct
2 Correct 33 ms 59992 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 12 ms 80732 KB Output is correct
6 Correct 4 ms 25180 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 55876 KB Output is correct
2 Correct 34 ms 62040 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 50 ms 55900 KB Output is correct
6 Correct 11 ms 70508 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 55892 KB Output is correct
2 Correct 37 ms 59944 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 11 ms 80476 KB Output is correct
6 Correct 5 ms 33116 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 60008 KB Output is correct
2 Correct 47 ms 57944 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 11 ms 70236 KB Output is correct
6 Correct 4 ms 24924 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49784 KB Output is correct
2 Correct 40 ms 57912 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 13 ms 90908 KB Output is correct
6 Correct 8 ms 53852 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 59976 KB Output is correct
2 Correct 42 ms 62036 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 45916 KB Output is correct
6 Correct 9 ms 62208 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 57936 KB Output is correct
2 Correct 43 ms 59976 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 47 ms 59984 KB Output is correct
6 Correct 12 ms 78684 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 53848 KB Output is correct
2 Correct 40 ms 57940 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 10 ms 64092 KB Output is correct
6 Correct 9 ms 66532 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43864 KB Output is correct
2 Correct 51 ms 64040 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 8 ms 53848 KB Output is correct
6 Correct 13 ms 93020 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 45608 KB Output is correct
2 Correct 46 ms 57940 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 22 ms 49748 KB Output is correct
6 Correct 7 ms 45556 KB Output is correct