Submission #1259856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259856		salles	Race (IOI11_race)	C++20	21 / 100	3094 ms	21060 KiB

race

#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;
}

//vetor que pode ser "zerado" para INT_MAX em O(1)
class VetorZeravelO1 {
private:
  int flagAtual;
  vector<int> melhorCaminho;
  vector<int> flagElementos; //flag usada em cada elemento
public:

  VetorZeravelO1(int n): flagAtual(1), melhorCaminho(n), flagElementos(n,0) {}

  //ao trocar a flag, todos valores ficam "zerados" (infinitos), pois usavam a flag antiga
  void zeraTodosValores() { 
    flagAtual++;
  }

  void set(int pos, int caminho) {
    if(ehInfinito(pos)) { //eh infinito!
      flagElementos[pos] = flagAtual;
      melhorCaminho[pos] = caminho;
    }
    melhorCaminho[pos] =caminho;
  }
  int get(int pos) {
    if(ehInfinito(pos)) return INT_MAX;
    else return melhorCaminho[pos];
  }
  bool ehInfinito(int pos) {
    return (flagElementos[pos]!=flagAtual); //se a flag for igual --> esta inicializado. Se nao for --> nao esta inicializado (eh infinito)
  }  
  int size() {
    return melhorCaminho.size();
  }
};

//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, 
                      VetorZeravelO1 &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.get(k - pesoParcial) != INT_MAX)
    mi = min( mi , melhor.get(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, 
                      VetorZeravelO1 &melhor, int pesoParcial, int tamParcial) {
  if(bloqueados[v]) return;  

  //qual o melhor caminho que passa na raiz e termina exatamente no vertice atual? 
  if(pesoParcial >= melhor.size()) return;  //atencao aqui! O peso parcial pode crescer e ficar bem maior que o K maximo, dando RE (tecnicamente eu poderia parar ao ultrapassar...)
  melhor.set(pesoParcial , min( tamParcial , melhor.get(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(VetorZeravelO1 &melhor, 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;
  melhor.zeraTodosValores(); //colocar infinito em todo vetor de melhores.
  
  //iniciar o melhor[0] ?
  melhor.set(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.get(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(melhor,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 ) );
  }

  VetorZeravelO1 melhor(1000123); //Vai dar TLE se ficar recriando sempre... usar auxiliar para marcar se esta preenchido ou nao


  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(melhor,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;*/
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57