oj.uz

Submission #674690

# Submission time Handle Problem Language Result Execution time Memory
674690 2022-12-25T19:31:28 Z Nicolas125841 Burza (COCI16_burza) C++14
160 / 160
 247 ms 9292 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define YES "DA"
#define NO "NE"
 
vector<vector<int>> layers;
vector<int> ways;
unordered_map<int, bitset<400>> coverage;
 
bitset<400> dfs(vector<vector<int>> &mp, int n, int p, int d, int k){
    if(layers.size() == d){
        layers.push_back(vector<int>());
        ways.push_back(0);
    }
 
    if(d == k){
        coverage[n] |= 1;
        coverage[n] <<= layers[d].size();
    }
 
    layers[d].push_back(n);
 
    for(int v : mp[n]){        
        if(v != p){
            bitset<400> res = dfs(mp, v, n, d+1, k);
 
            if(layers.size() > k && d < k)
                coverage[n] |= res;           
        }
    }
 
    if(coverage[n] != 0)
        ways[d]++;

    return coverage[n];
}
 
int main(){
    cin.tie(NULL)->sync_with_stdio(false);
 
    int n, k;
    cin >> n >> k;
 
    vector<vector<int>> mp(n, vector<int>());    
 
    for(int i = 0; i < n-1; i++){
 
        int u, v;
        cin >> u >> v;
 
        mp[--u].push_back(--v);
        mp[v].push_back(u);
 
    }
    
    dfs(mp, 0, -1, 0, k);
    
    if(layers.size() <= k)
        cout << YES << "\n";
    else{
        unordered_set<bitset<400>> cur, prev = {bitset<400>()};
        bool g = false;
 
        for(int i = 1; i <= k; i++){
            for(bitset<400> bs : prev){
                int cnt = bs.count();                
                for(int v : layers[i]){
                    int ccnt = coverage[v].count();
                    if(coverage[v] == 0 || (ccnt == 1 && layers[k].size()-cnt > (k-i)+1))
                        continue;

                    if((coverage[v] & bs) == 0){
                        cur.insert(coverage[v] | bs);

                        if(layers[k].size()-(ccnt+cnt) <= k-i){
                            g = true;
                            break;
                        }
                    }                
                }
                if(g)
                    break;
            }
 
            assert(cur.size() <= 150000);

            swap(cur, prev);
            cur.clear();

            if(g)
                break;
        }
 
        cout << (g ? YES : NO) << "\n";
    }
 
    
}

Compilation message

burza.cpp: In function 'std::bitset<400> dfs(std::vector<std::vector<int> >&, int, int, int, int)':
burza.cpp:13:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   13 |     if(layers.size() == d){
      |        ~~~~~~~~~~~~~~^~~~
burza.cpp:29:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |             if(layers.size() > k && d < k)
      |                ~~~~~~~~~~~~~~^~~
burza.cpp: In function 'int main()':
burza.cpp:60:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |     if(layers.size() <= k)
      |        ~~~~~~~~~~~~~~^~~~
burza.cpp:71:79: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |                     if(coverage[v] == 0 || (ccnt == 1 && layers[k].size()-cnt > (k-i)+1))
      |                                                          ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
burza.cpp:77:56: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |                         if(layers[k].size()-(ccnt+cnt) <= k-i){
      |                            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 852 KB Output is correct
2 Correct 227 ms 4764 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 4828 KB Output is correct
2 Correct 228 ms 4656 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 106 ms 2508 KB Output is correct
6 Correct 3 ms 980 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 4752 KB Output is correct
2 Correct 231 ms 4668 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1492 KB Output is correct
2 Correct 240 ms 4752 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 448 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 4864 KB Output is correct
2 Correct 247 ms 4656 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 48 ms 9292 KB Output is correct
6 Correct 2 ms 596 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 4728 KB Output is correct
2 Correct 239 ms 4724 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 4744 KB Output is correct
2 Correct 243 ms 4792 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 108 ms 2448 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1416 KB Output is correct
2 Correct 239 ms 4764 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 936 KB Output is correct
2 Correct 246 ms 4756 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 3 ms 596 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 2444 KB Output is correct
2 Correct 223 ms 4768 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 50 ms 1404 KB Output is correct
6 Correct 0 ms 340 KB Output is correct