Submission #471408

#	Time	Username	Problem	Language	Result	Execution time	Memory
471408		cookiemonster04	Burza (COCI16_burza)	C++17	0 / 160	1 ms	332 KiB

burza

#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 >= 9) {
        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);
    while(K > 0 && !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 val : thing[idx]) {
            for (int to : adj[val]) {
                if (to != par[val] && to != best) {
                    thing[nidx].pb(to);
                }
            }
        }
        thing[idx].clear();
        idx = nidx;
        nidx = 1 ^ nidx;
        K--;
    }
    if (K == 0 && !thing[idx].empty()) {
        cout << "NE" << endl;
    }
    else {
        cout << "DA" << endl;
    }
    return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 16
• Subtask 3: 0 / 16
• Subtask 4: 0 / 16
• Subtask 5: 0 / 16
• Subtask 6: 0 / 16
• Subtask 7: 0 / 16
• Subtask 8: 0 / 16
• Subtask 9: 0 / 16
• Subtask 10: 0 / 16