oj.uz

Submission #782384

# Submission time Handle Problem Language Result Execution time Memory
782384 2023-07-13T22:02:06 Z vgoofficial Burza (COCI16_burza) C++14
160 / 160
 357 ms 15564 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n,k;
vector<vector<int>> edges;
vector<int> depth;
vector<int> parents;
vector<vector<int>> depths(400);
int maxDepth(int i, int dpth) {
    depth[i]=dpth;
    int maxD = dpth;
    for(int j = 0; j < edges[i].size(); j++) {
        int l = edges[i][j];
        if(depth[l]!=-1) continue;
        if(dpth==k) {
            edges[i][j]=-1;
        } else {
            if(maxDepth(l, dpth+1)!=k) {
                edges[i][j]=-1;

            } else {
                parents[l]=i;
                maxD=k;
            }
        }
    }
    if(maxD==k) {
        depths[dpth].push_back(i);
    }
    return maxD;
}
struct state {
    int level;
    vector<int> mustConsider;
    state(int level, vector<int> unaccessible) {
        this->mustConsider = unaccessible;
        this->level = level;
    }
};
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);
    cin >> n >> k;
    if(k * k>n) {
        cout << "DA" << endl;
        return 0;
    }
    edges=vector<vector<int>>(n);
    depth=vector<int>(n, -1);
    parents=vector<int>(n, -1);
    depth[0]=0;
    for(int i = 1; i < n; i++) {
        int a,b;
        cin >> a >> b;
        edges[a-1].push_back(b-1);
        edges[b-1].push_back(a-1);
    }
    maxDepth(0, 0);
    /*
    for(int i = 0; i < n; i++) {
        cout << i << " " << depth[i] << " " << parents[i] << endl;
        for(int j: depths[i]) {
            cout << j << " ";
        }
        cout << endl;
        for(int j: edges[i]) {
            cout << j << " ";
        }
        cout << endl;
    }
    */
    deque<vector<int>> q;
    q.push_back(vector<int>(1,0));
    set<vector<int>> vis;
    while(q.size()) {
        vector<int> s = q.front();
        q.pop_front();
        if(s.size()==0) {
            cout << "DA" << endl;
            return 0;
        }
        int remain = k-depth[s[0]];
        vector<int> next;
        for(int i: s) {
            for(int j: edges[i]) {
                if(j==-1) continue;
                if(j==parents[i]) continue;
                next.push_back(j);
            }
        }
        if(next.size()>remain) {
            continue;
        }
        for(int i = 0; i < next.size(); i++) {
            swap(next[i], next.back());
            vector<int> temp = next;
            temp.pop_back();
            sort(begin(temp), end(temp));
            if(!vis.count(temp)) {
                q.push_back(temp);
                vis.insert(temp);
            }
            swap(next[i], next.back());
        }
    }
    cout << "NE" << endl;
}

Compilation message

burza.cpp: In function 'int maxDepth(int, int)':
burza.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int j = 0; j < edges[i].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~~~
burza.cpp: In function 'int main()':
burza.cpp:91:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |         if(next.size()>remain) {
      |            ~~~~~~~~~~~^~~~~~~
burza.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int i = 0; i < next.size(); i++) {
      |                        ~~^~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2100 KB Output is correct
2 Correct 355 ms 15416 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 444 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 15444 KB Output is correct
2 Correct 355 ms 15564 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 341 ms 15452 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 15432 KB Output is correct
2 Correct 349 ms 15460 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 4096 KB Output is correct
2 Correct 344 ms 15488 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 15404 KB Output is correct
2 Correct 353 ms 15536 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 15468 KB Output is correct
2 Correct 344 ms 15460 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 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 347 ms 15428 KB Output is correct
2 Correct 357 ms 15492 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 344 ms 15376 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 68 ms 3980 KB Output is correct
2 Correct 356 ms 15384 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 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 30 ms 2184 KB Output is correct
2 Correct 347 ms 15500 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 7856 KB Output is correct
2 Correct 354 ms 15468 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 171 ms 7920 KB Output is correct
6 Correct 1 ms 340 KB Output is correct