oj.uz

Submission #918451

# Submission time Handle Problem Language Result Execution time Memory
918451 2024-01-29T20:52:11 Z PikaChu999 Burza (COCI16_burza) C++14
0 / 160
 7 ms 4700 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];
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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 2908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2652 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Incorrect 5 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2652 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 0 ms 600 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 7 ms 2652 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 476 KB Output is correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2652 KB Output is correct
2 Correct 6 ms 4700 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 2908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2524 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 2908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 6 ms 2648 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 7 ms 2580 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 6 ms 2652 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 476 KB Output is correct
5 Incorrect 3 ms 2656 KB Output isn't correct
6 Halted 0 ms 0 KB -