Submission #660083

#	Time	Username	Problem	Language	Result	Execution time	Memory
660083		BlancaHM	Burza (COCI16_burza)	C++14	160 / 160	59 ms	856 KiB

burza

#include <iostream>
#include <vector>
using namespace std;

int N, K;
vector<vector<int>> adjList, nodosPorProfundidad;
vector<int> hojas, hojaIzq, hojaDer, DP;
vector<bool> visitado;

void dfs(int nodo, int profundidad) {
    visitado[nodo] = true;
    if (profundidad == K) {
        hojas.push_back(nodo);
        nodosPorProfundidad[profundidad].push_back(nodo);
        hojaIzq[nodo] = (int) hojas.size();
        hojaDer[nodo] = (int) hojas.size();
        return;
    }
    nodosPorProfundidad[profundidad].push_back(nodo);
    for (int vecino: adjList[nodo]) {
        if (!visitado[vecino]) {
            dfs(vecino, profundidad+1);
            hojaIzq[nodo] = min(hojaIzq[nodo], hojaIzq[vecino]);
            hojaDer[nodo] = max(hojaDer[nodo], hojaDer[vecino]);
        }
    }
}

int calcDP(int mascara) {
    if (DP[mascara] != -1) return DP[mascara];
    int ans = 0;
    for (int i = 0; i < K; i++) {
        if (mascara & (1<<i)) {
            int mascaraVieja = mascara - (1<<i);
            int dpVieja = calcDP(mascaraVieja);
            ans = max(ans, dpVieja);
            for (int nodo: nodosPorProfundidad[i+1]) {
                if (hojaIzq[nodo]-1 <= dpVieja) ans = max(ans, hojaDer[nodo]);
            }
        }
    }
    //cout << "dp: " << mascara << ' ' << ans << endl;
    return DP[mascara] = ans;
}

bool esPosible() {
    visitado.assign(N, false);
    hojaIzq.assign(N, N);
    hojaDer.assign(N, -1);
    nodosPorProfundidad.assign(K+1, vector<int>());
    dfs(0, 0);
    /*for (int i = 0; i < N; i++) cout << hojaIzq[i] << ' ';
    cout << endl;
    for (int i = 0; i < N; i++) cout << hojaDer[i] << ' ';
    cout << endl;*/
    int numHojas = (int) hojas.size();
    DP.assign(1<<K, -1);
    DP[0] = 0;
    return calcDP((1<<K) - 1) == numHojas;
}

int main() {
    cin >> N >> K;
    adjList = vector<vector<int>>(N);
    int A, B;
    for (int i = 0; i < N-1; i++) {
        cin >> A >> B;
        adjList[A-1].push_back(B-1);
        adjList[B-1].push_back(A-1);
    }
    if (K*K >= N || esPosible()) cout << "DA\n";
    else cout << "NE\n";
    return 0;
}

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