제출 #660087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660087		BlancaHM	Burza (COCI16_burza)	C++14	160 / 160	73 ms	852 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;

/*
Hacemos una dfs para calcular, para cada nodo con profundidad <= k:
- su profundidad, añadiéndolo a nodosPorProfundidad en la capa correspondiente
- si su profundidad es K, lo añadiremos a nuestra lista de hojas
- hojasIzq[nodo]: el índice dentro de la lista de hojas (empezando con 1) de la hoja más
  a la izquierda en el subárbol de nodo
- hojasDer[nodo]: el índice dentro de la lista de hojas (empezando con 1) de la hoja más
  a la derecha en el subárbol de nodo
*/
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]);
        }
    }
}

/*
DP[mascara] guarda, quitando un nodo en cada capa de la máscara, la longitud del máximo
prefijo de hojas que podremos cubrir.

Dada una máscara, probamos a quitar de cada capa incluida cada nodo incluido.
Miramos el valor de la DP en esa máscara sin la capa quitada y vemos si la unión
de ese valor y las hojas cubiertas por el nodo quitado aumenta el récord actual,
en cuyo caso lo actualizamos.
*/
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]);
            }
        }
    }
    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);
    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