Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2430
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2430
Catálogo de Músicas
Por OBI - Olimpíada Brasileira de Informática 2013 
Brazil
Timelimit: 1
Joyce é uma menina que gosta muito de ouvir música, e possui uma enorme coleção de músicas num dvd. Ela é uma menina organizada e deixa suas músicas em pastas, mas como o número de músicas e de pastas é grandre, Joyce construiu um catálogo para melhor localizá-las.
Para o catálogo Joyce utilizou uma convenção usual em sistemas operacionais, em que a descrição da localiza- ção de cada arquivo é formada pela sequência dos nomes das pastas no caminho da raiz do dvd até o arquivo, separados pelo caractere barra (‘/’). Por exemplo, na figura abaixo, a descrição da música Sampa.mp3 no catálogo é MPB/Caetano/Sampa.mp3.
Utilizando essa convenção, o catálogo do dvd mostrado na figura é:
Rock/AngraCarryOn.mp3
MPB/Caetano/Sampa.mp3
MPB/Cartola/Alvorada.mp3
Como o dvd de Joyce tem muitas músicas e pastas, o catálogo é muito grande. Joyce notou no entanto que o catálogo poderia ser menor (ter um número menor de caracteres) caso ela utilizasse outro conceito usual na nomeação de arquivos em sistemas operacionais: usar uma pasta como referência, ao invés da raiz.
Se uma pasta diferente da raiz for escolhida como referência, então para todos os arquivos que estejam diretamente nessa pasta ou em alguma subpasta não será mais necessário escrever o nome da pasta referência no catálogo. Para as demais pastas, é necessário indicar o caminho utilizando as pastas acima (na direção da raiz) utilizando a convenção ‘../’ para a pasta imediatamente acima da pasta referência. No exemplo da figura acima, no caso de a referência ser a pasta Caetano, a música Sampa.mp3 seria simplesmente descrita como Sampa.mp3. Já a música Alvorada.mp3 seria descrita como ../Cartola/Alvorada.mp3.
Assim, se a pasta Caetano for utilizada como referência, o catálogo será:
../../Rock/AngraCarryOn.mp3
Sampa.mp3
../Cartola/Alvorada.mp3
Nesse caso, a descrição do catálogo tem 59 carateres, menor do que quando a referência utilizada é a raiz do DVD.
Seu objetivo é, dada a informação de todas as músicas do catálogo, determinar o número mínimo de caracteres necessários para descrever o catálogo.
Entrada
A primeira linha da entrada contém um inteiro N (1 ≤ N ≤ 105), indicando quantos arquivos Joyce possui no dvd. Cada uma das N linhas seguintes contém a descrição de um arquivo, a partir da raiz.
- Número de pastas na entrada ≤ 105
- O nome de cada pasta e de cada arquivo é composto por no máximo 20 caracteres, entre letras minúsculas, maiúsculas e ponto (.)
- Cada pasta possui no máximo 100 pastas como filhas diretas.
Saída
Seu programa deve imprimir uma única linha, contendo apenas um inteiro, o número mínimo de caracteres necessários para descrever o catálogo.
| Exemplos de Entrada | Exemplos de Saída |
|
3 Rock/AngraCarryOn.mp3 MPB/Caetano/Sampa.mp3 MPB/Cartola/Alvorada.mp3 |
59 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 3 * 1e5 + 10;
int ponteiro, N, n, tam[MAXN], filhos[MAXN], nivel[MAXN], total, resp;
set < int> grafo[MAXN];
map conversao;
void dfs1(int x) {
filhos[x] = 0;
for (set < int>::iterator it = grafo[x].begin(); it != grafo[x].end(); it++) {
int v = *it;
nivel[v] = nivel[x] + 1;
dfs1(v);
filhos[x] += filhos[v];
}
if (filhos[x] == 0) filhos[x] = 1;
}
void dfs2(int x, int salva, int acumulada) {
if (grafo[x].size() == 0) return;
int proximo_acumulada = (N - filhos[x]) * 3 + acumulada;
int proximo_salva = salva + (tam[x] + (x != 0)) * (filhos[x]);
if (x != 0) {
int temporario = total - proximo_salva + proximo_acumulada;
resp = min(resp, temporario);
}
for (set < int>::iterator it = grafo[x].begin(); it != grafo[x].end(); it++) {
int v = *it;
dfs2(v, proximo_salva, proximo_acumulada);
}
}
int main() {
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
cin >> n;
N = n;
while (n--) {
string entrada, temp;
vector < string> vetorzao;
vector<int> arestas;
arestas.push_back(0);
cin >> entrada;
resp += entrada.size();
total += entrada.size();
for (int i = 0; i < entrada.size(); i++) {
if (entrada[i] == '/') {
vetorzao.push_back(temp);
temp.clear();
} else {
temp.push_back(entrada[i]);
}
}
vetorzao.push_back(temp);
for (int i = 0; i < vetorzao.size(); i++) {
if (!conversao.count(vetorzao[i])) {
conversao[vetorzao[i]] = ++ponteiro;
tam[ponteiro] = vetorzao[i].size();
}
arestas.push_back(conversao[vetorzao[i]]);
}
for (int i = 0; i + 1 < arestas.size(); i++) {
grafo[arestas[i]].insert(arestas[i + 1]);
}
}
n = ponteiro;
dfs1(0);
// for(int i= 0;i < = n; i++){
// printf("Vertice %d Filhos %d Nivel %d :",i,filhos[i],nivel[i]);
// for(set < int>::iterator it = grafo[i].begin();it !=
// grafo[i].end();it++){ printf(" %d",*it);
// }
// printf("\n");
// }
dfs2(0, 0, 0);
cout << resp << endl;
return 0;
}
Input
Rock/AngraCarryOn.mp3
MPB/Caetano/Sampa.mp3
MPB/Cartola/Alvorada.mp3
Output