oj.uz

Submission #392844

# Submission time Handle Problem Language Result Execution time Memory
392844 2021-04-21T21:58:36 Z SirCovidThe19th Burza (COCI16_burza) C++14
160 / 160
 168 ms 12748 KB 
#include <bits/stdc++.h>
using namespace std;

int n, k;

vector<int> intervalL;
vector<int> intervalR;
vector<int> depth;

vector<vector<int>> adjList;
vector<vector<int>> check;
int track = 0;

void dfs(int node, int parent){
    if (depth[node] == k){
        intervalL[node] = track;
        intervalR[node] = track;
        track++;
    }
    else{
        for (int child : adjList[node]){
            if (child == parent) continue;
            depth[child] = depth[node]+1;
            dfs(child, node);
            intervalL[node] = min(intervalL[child], intervalL[node]);
            intervalR[node] = max(intervalR[child], intervalR[node]);
        }
    }
    if (node != 0 and intervalR[node] != -1){
        check[intervalR[node]].push_back(node);
    }
}
int main(){
    cin >> n >> k;
    adjList.resize(n);
    depth.resize(n);
    intervalL.resize(n);
    intervalR.resize(n);
    check.resize(n);
 
    depth[0] = 0;
    fill(intervalL.begin(), intervalL.end(), 1000000007);
    fill(intervalR.begin(), intervalR.end(), -1);
 
    for (int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        adjList[a-1].push_back(b-1);
        adjList[b-1].push_back(a-1);
    }
    if (k*k >= n){
        cout<<"DA";
        return 0;
    }
    dfs(0, 0);
    bool valid = false;
    //dp[i][j] - can we use only nodes of depths in subset i such 
    //that we cannot get to the first j nodes at depth K
    bool dp[(1<<k)][track+1];
    memset(dp, false, sizeof(dp));
    dp[0][0] = true;
    for (int i = 0; i < (1<<k); i++){
        //can we fill interval [1, j]
        for (int j = 1; j <= track; j++){
            //go through all points going to j
            for (int node : check[j-1]){
                //make sure depth is in subset
                if ((i&(1<<depth[node]-1)) != 0){
                    dp[i][j] = dp[i][j] or (dp[i^(1<<depth[node]-1)][intervalL[node]-1+1]);
                }
            }
        }
        if (dp[i][track])
            valid = true;
    }
    if (valid)
        cout<<"DA";
    else
        cout<<"NE";
    
}

Compilation message

burza.cpp: In function 'int main()':
burza.cpp:68:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   68 |                 if ((i&(1<<depth[node]-1)) != 0){
burza.cpp:69:65: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   69 |                     dp[i][j] = dp[i][j] or (dp[i^(1<<depth[node]-1)][intervalL[node]-1+1]);

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1740 KB Output is correct
2 Correct 155 ms 12364 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 10948 KB Output is correct
2 Correct 161 ms 10444 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 146 ms 10580 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 10700 KB Output is correct
2 Correct 137 ms 10704 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 4300 KB Output is correct
2 Correct 146 ms 12748 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 9164 KB Output is correct
2 Correct 142 ms 10188 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 11340 KB Output is correct
2 Correct 133 ms 9932 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 10964 KB Output is correct
2 Correct 138 ms 10436 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 143 ms 9676 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3148 KB Output is correct
2 Correct 146 ms 11736 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1460 KB Output is correct
2 Correct 168 ms 11852 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 292 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 4284 KB Output is correct
2 Correct 149 ms 11988 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 65 ms 4428 KB Output is correct
6 Correct 1 ms 204 KB Output is correct