oj.uz

Submission #782368

# Submission time Handle Problem Language Result Execution time Memory
782368 2023-07-13T21:12:52 Z vgoofficial Burza (COCI16_burza) C++14
0 / 160
 1000 ms 388 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;
}
bool dfs2(int level, vector<bool> &unaccessible) {
    /*
    cout << "dfs2 called " << level << endl;
    for(int i = 0; i < n; i++) {
        cout << unaccessible[i] << " ";
    }
    cout << endl;
    */
    int notDone = 0;
    for(int i: depths[level]) {
        //cout << i << " " << parents[i] << endl;
        if(unaccessible[parents[i]]) {
            unaccessible[i]=true;
        } else {
            unaccessible[i]=false;
            notDone++;
        }
    }
    /*
    for(int i = 0; i < n; i++) {
        cout << unaccessible[i] << " ";
    }
    cout << endl;
    */
    if(notDone<2) return true;
    if(level==k) return false;
    for(int i: depths[level]) {
        if(!unaccessible[i]) {
            unaccessible[i]=true;
            if(dfs2(level+1, unaccessible)) {
                return true;
            }
            unaccessible[i]=false;
        }
    }
    return false;
}
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;
    }
    */
    vector<bool> unacc(n);
    if(dfs2(1, unacc)) {
        cout << "DA" << endl;
    } else {
        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++) {
      |                    ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 340 KB Time limit exceeded
2 Halted 0 ms 0 KB -