oj.uz

Submission #918463

# Submission time Handle Problem Language Result Execution time Memory
918463 2024-01-29T21:13:59 Z vjudge1 Burza (COCI16_burza) C++11
160 / 160
 50 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 12 ms 51800 KB Output is correct
2 Correct 34 ms 60064 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 12 ms 80676 KB Output is correct
6 Correct 4 ms 24924 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 55900 KB Output is correct
2 Correct 34 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 49 ms 55888 KB Output is correct
6 Correct 11 ms 70488 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 56404 KB Output is correct
2 Correct 37 ms 60004 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 12 ms 80688 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 19 ms 59996 KB Output is correct
2 Correct 46 ms 57976 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 10 ms 70324 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 49716 KB Output is correct
2 Correct 40 ms 57988 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 13 ms 90968 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 42 ms 59980 KB Output is correct
2 Correct 41 ms 62036 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 7 ms 46168 KB Output is correct
6 Correct 8 ms 62044 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 57932 KB Output is correct
2 Correct 42 ms 59984 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 48 ms 60244 KB Output is correct
6 Correct 12 ms 78680 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 41 ms 57952 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 10 ms 64092 KB Output is correct
6 Correct 9 ms 66396 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 43612 KB Output is correct
2 Correct 50 ms 64080 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 9 ms 53852 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 22 ms 45640 KB Output is correct
2 Correct 46 ms 57948 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 22 ms 49732 KB Output is correct
6 Correct 7 ms 45660 KB Output is correct