catalogo_de_musicas.cpp

//
//  catalogo_de_musicas.cpp
//
//  Created by Lucca Siaudzionis on 31/03/14.
//
//  Catálogo de Músicas - OBI 2013 P2 F1

#include <map>
#include <string>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define MAXN 100100


//variáveis------------------
int nfiles;
int nfolder;
int pai[MAXN];    //quem é a pasta pai
int cost[MAXN]; //custo que é usar esta pasta como referência
int size[MAXN];   //tamanho de digitação de uma pasta
int files[MAXN];  //guarda a qtd de arquivos que você vai chegar descendo esta pasta
vector<int> sons[MAXN]; //guarda quem são as pastas filhotes
map<string, int>  mapa; //converte o nome da ba
//--------------------------

void Read(){
    scanf("%d",&nfiles);
    
    files[0] = nfiles;
    for(int i = 1;i <= nfiles;i++){
        string arquivo;
        cin >> arquivo;
        
        cost[0] += arquivo.size();
        
        int ultimo = 0; //dvd
        string atual;
        
        for(int i = 0;i < arquivo.size();i++){
            atual += arquivo[i];
            
            if(i == arquivo.size() - 1){
                atual.clear();
                break;
            }
            
            if(atual[atual.size()-1] == '/'){
                
                if( !mapa[atual] ){
                    mapa[atual] = ++nfolder;
                    pai[nfolder] = ultimo;
                    size[nfolder] = atual.size();
                    sons[ultimo].push_back(nfolder);
                }
                
                files[ mapa[atual] ]++;
                ultimo = mapa[atual];
                
                atual.clear();
            }
            
        }
        
    }
    
}

void Calc_Cost(int pos){
    cost[pos] = cost[ pai[pos] ] - size[pos]*files[pos] + 3*(nfiles - files[pos]);
    for(int i = 0;i < sons[pos].size();i++) Calc_Cost(sons[pos][i]);
}

int main(){
    Read();
    
    for(int i = 0;i < sons[0].size();i++) Calc_Cost(sons[0][i]);
    
    int small = 999999999;
    for(int i = 0;i <= nfolder;i++) small = min(small, cost[i]);
    printf("%d\n",small);
    
}