oj.uz

Submission #660083

# Submission time Handle Problem Language Result Execution time Memory
660083 2022-11-20T10:24:48 Z BlancaHM Burza (COCI16_burza) C++14
160 / 160
 59 ms 856 KB 
#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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 50 ms 852 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 852 KB Output is correct
2 Correct 49 ms 852 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 52 ms 856 KB Output is correct
6 Correct 1 ms 296 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 852 KB Output is correct
2 Correct 52 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 472 KB Output is correct
2 Correct 52 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 852 KB Output is correct
2 Correct 51 ms 852 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 852 KB Output is correct
2 Correct 50 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 852 KB Output is correct
2 Correct 50 ms 836 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 50 ms 852 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 424 KB Output is correct
2 Correct 49 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 53 ms 852 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 556 KB Output is correct
2 Correct 57 ms 836 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 23 ms 468 KB Output is correct
6 Correct 1 ms 212 KB Output is correct