oj.uz

Submission #471409

# Submission time Handle Problem Language Result Execution time Memory
471409 2021-09-09T04:06:48 Z cookiemonster04 Burza (COCI16_burza) C++17
0 / 160
 1 ms 332 KB 
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back

/* Date: 9/8/21
 * Link: https://oj.uz/problem/view/COCI16_burza
 * Verdict: 
*/

vector<int> alive(405);
vector<int> adj[405];
vector<int> depth(405);
vector<int> par(405);
int N, K;
void dfs(int p = -1, int c = 0) {
    par[c] = p;
    if (depth[c] == K) {
        alive[c] = 1;
        return;
    }
    for (int to : adj[c]) {
        if (to == p) continue;
        depth[to] = depth[c]+1;
        dfs(c, to);
        alive[c] += alive[to];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> N >> K;
    if (K >= 15) {
        cout << "DA" << endl;
        return 0;
    }
    fill(alive.begin(), alive.end(), 0);
    for (int i = 0; i < N-1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].pb(b); adj[b].pb(a);
    }
    depth[0] = 0;
    dfs();
    int idx = 0, nidx = 1;
    vector<int> thing[2];
    thing[0].pb(0);
    int step = 0;
    while(!thing[idx].empty()) {
        int best = -1, bestalive = -1;
        for (int node : thing[idx]) {
            for (int op : adj[node]) {
                if (op == par[node]) continue;
                if (alive[op] > bestalive) {
                    best = op; bestalive = alive[op];
                }
            }
        }
        for (int node : thing[idx]) {
            for (int op : adj[node]) {
                if (op != par[node] && op != best) {
                    thing[nidx].pb(op);
                }
            }
        }
        thing[idx].clear();
        idx = nidx;
        nidx = 1 ^ nidx;
        step++;
    }
    if (step > K) {
        cout << "NE" << endl;
    }
    else {
        cout << "DA" << endl;
    }
    return 0;
}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 16.0

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

Subtask #6
0 / 16.0

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

Subtask #7
0 / 16.0

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

Subtask #8
0 / 16.0

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

Subtask #9
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 16.0

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