Submission #1259848

#TimeUsernameProblemLanguageResultExecution timeMemory
1259848sallesRace (IOI11_race)C++20
0 / 100
167 ms196192 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; //calcula o tamanho da subarvore void dfs( vector<vector< pair<int,int> > > &adj, vector<int> &subtreeSz, int v, int pai) { int tam = 1; //tamanho = 1 + tam dos filhos for(auto &[w,peso]:adj[v]) if(w!=pai) { dfs(adj,subtreeSz,w,v); tam += subtreeSz[w]; } subtreeSz[v] = tam; } //percorre todos os vertices e retorna o centroide... //como os componentes vao mudando de tamanho (a medida em que vertices sao bloqueados), temos que passar isso... int findCentroid( vector<vector< pair<int,int> > > &adj, vector<int> &subtreeSz, vector<int> &bloqueados, int numVertComponente, int v, int pai) { //se todas subarvores geradas ao remover v ficam com tamanho <= n/2 --> v eh centroide.. bool ehCentroide = true; int tamCima = numVertComponente - subtreeSz[v]; //tamanho da parte de "cima da arvore" (cc do pai de v, se v for removido) if(tamCima > numVertComponente/2) ehCentroide = false; for(auto &[w,peso]:adj[v]) if(w!=pai && !bloqueados[w]) { //confere os filhos if(subtreeSz[w] > numVertComponente/2) { ehCentroide = false; break; } } if(ehCentroide) return v; //se nao for v, entao eh um dos filhos... for(auto &[w,peso]:adj[v]) if(w!=pai && !bloqueados[w]) { int ans = findCentroid(adj,subtreeSz,bloqueados,numVertComponente, w,v); if(ans!=-1) return ans; } return -1; //nao achou nesta subarvore... } //melhor caminho que termina no vertice v, tendo distancia total k //calcula para cada distancia possivel //peso parcial tem o peso parcial da raiz ate v, tamParcial tem o mesmo para o tamanho int melhorTerminando(int v, int pai, vector<vector< pair<int,int> > > &adj, vector<int> &bloqueados, vector<int> &melhor, int k, int pesoParcial, int tamParcial) { if(bloqueados[v]) return INT_MAX; if(pesoParcial > k) return INT_MAX; //ultrapassei o peso! nao tem jeito int mi= INT_MAX; //qual o melhor caminho que passa na raiz e termina exatamente no vertice atual? //ele tem tamanho melhor[k - pesoParcial] do filho anterior ate a raiz + tamParcial da raiz ate v if(melhor[k - pesoParcial] != INT_MAX) mi = min( mi , melhor[k - pesoParcial] + tamParcial ); //qual o melhor que termina em algum dos filhos (ou mais para baixo)? for(auto &[w,peso]: adj[v]) if(w!=pai && !bloqueados[w]) { mi = min(mi, melhorTerminando(w,v, adj,bloqueados, melhor, k, pesoParcial + peso, tamParcial+1)); } return mi; } //calcula o melhor de cada peso que vai de v ateh a raiz void calculaMelhorTerminandoRaiz(int v, int pai, vector<vector< pair<int,int> > > &adj, vector<int> &bloqueados, vector<int> &melhor, int pesoParcial, int tamParcial) { if(bloqueados[v]) return; //qual o melhor caminho que passa na raiz e termina exatamente no vertice atual? melhor[pesoParcial] = min( tamParcial , melhor[pesoParcial] ); //qual o melhor que termina em algum dos filhos (ou mais para baixo)? for(auto &[w,peso]: adj[v]) if(w!=pai && !bloqueados[w]) { calculaMelhorTerminandoRaiz(w,v, adj,bloqueados, melhor, pesoParcial + peso, tamParcial+1); } } //Encontra o melhor caminho de peso k no CC de v, considerando que os vertices "testados" estao bloqueados (ou seja, eles dividem a arvore em varios CCs) int encontraMelhorCaminho(vector<vector< pair<int,int> > > &adj, vector<int> &subtreeSz, vector<int> &bloqueados, int numVertComponente, int k, int v) { int mi= INT_MAX; //cerr << endl << endl; //cerr << "V = " << v << " tam " << numVertComponente << endl; //ou o caminho com o minimo de arestas passa pela raiz ou nao. //vamos escolher o centroide como nova raiz da arvore atual... int centroide = findCentroid(adj, subtreeSz, bloqueados, numVertComponente, v, -1); //cerr << "Calculando com centroide " << centroide << endl; vector<int> melhor(1000123, INT_MAX); //Vai dar TLE //iniciar o melhor[0] ? melhor[0] = 0; //encontre o melhor caminho que passa pelo centroide... for(auto &[w,peso]:adj[centroide]) if(!bloqueados[w]) { //para cada filho w, vamos calcular o menor caminho de distancia 0, de distancia 1, de distancia 2, .... //e que termina em v (logo apos passar por w) //ANTES DISSO, eu atualizo o melhor que comeca no componente de um filho ja processado e termina no do filho atual // melhor[i] jah tem o melhor caminho de comprimento i que passa em um filho anterior e termina em v int melhorComecaFilhoTerminaW = melhorTerminando(w, centroide, adj, bloqueados, melhor,k, peso, 1); mi = min( mi, melhorComecaFilhoTerminaW); //cout << "Melhor termina w " << w << " " << melhorComecaFilhoTerminaW << endl; //agora, fazemos uma DFS para incluir no contador "melhor" os melhores de cada tamanho que terminam em v... calculaMelhorTerminandoRaiz(w, centroide, adj, bloqueados,melhor,peso,1); /*cout << "Apos filho w " << w << endl; for(int i=0;i<100000;i++) if(melhor[i]!=INT_MAX) cout << i << " " << melhor[i] << endl; cout << endl;*/ } //considerar melhor que comeca em um filho e termina na raiz, tendo peso exatamente k mi = min(mi, melhor[k]); //encontre o melhor caminho estao completamente nas subarvores dos filhos, nao passando por esse centroide bloqueados[centroide] = true; //bloqueia, dividindo a arvore em mais CCs for(auto &[w,peso]:adj[centroide]) if(!bloqueados[w]) { int melhorDoFilho = encontraMelhorCaminho(adj,subtreeSz,bloqueados,subtreeSz[w],k,w); mi = min(mi,melhorDoFilho); } return mi; } int best_path(int n, int k, int H[][2], int L[]) { vector<vector< pair<int,int> > > adj(n); for(int i=0;i<n-1;i++) { int a = H[i][0]; int b = H[i][1]; int w = L[i]; adj[a].push_back(make_pair(b,w ) ); adj[b].push_back(make_pair(a,w ) ); } vector<int> subtreeSz(n); dfs(adj,subtreeSz,0,-1); //calcula o tamanho das subarvores, escolhendo 0 (arbitrariamente) como raiz vector<int> bloqueados(n); int mi = encontraMelhorCaminho(adj,subtreeSz,bloqueados,n,k,0); if(mi==INT_MAX) mi = -1; return mi; /*int mi= INT_MAX; for(int i=0;i<n;i++) { vector<int> visit(n,false); int ans = melhor(i,adj,visit,k); mi = min(mi, ans); } if(mi==INT_MAX) mi = -1; return mi;*/ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...