Solução OBI 2013

catalogo.cpp

// Ivan Carvalho
// Catálogo de Músicas - Fase 1 Programação Nível 2 - OBI 2013
// O(n*log(n))
#include <bits/stdc++.h>
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<string,int> 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 >> 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;
}