제출 #660087

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
660087	2022-11-20 10:33:49	BlancaHM	Burza (COCI16_burza)	C++14	160 / 160	73 ms	852 KiB

burza

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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]) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• 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