Submission #1245752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245752		Gabriel	Werewolf (IOI18_werewolf)	C++20	0 / 100	312 ms	116640 KiB

werewolf

#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
vector< vector<int> > Grafo, Visitados;
vector< vector< pair<int, int> > > Mesa_dispersa_menor, Mesa_dispersa_mayor;
vector<int> Orden, iOrden;
vector<bool> Visitadoss;
int Tiempo = 0, Inicio, Final;
struct Responder_esto{
  int Mayor, Menor;
};
struct Consultita{
  int Inicio, Final, Izquierda, Derecha, _ndice;
};
bool operator<(const Consultita& a, const Consultita& b){
  if(a.Izquierda < b.Izquierda) return 1;
  if(b.Izquierda < a.Izquierda) return 0;
  if(a.Derecha < b.Derecha) return 1;
  if(b.Derecha < a.Derecha) return 0;
  return a._ndice < b._ndice;
}
void Crear(int Nodo, int Anterior){
  //cerr<<Nodo<<" "<<Anterior<<"\n";
  Orden[Nodo] = Tiempo;
  iOrden[Tiempo] = Nodo;
  Visitadoss[Nodo] = 1;
  Tiempo++;
  if(Anterior != -2){
    Mesa_dispersa_menor[Nodo].push_back({min(Nodo, Anterior), Anterior});
    Mesa_dispersa_mayor[Nodo].push_back({max(Nodo, Anterior), Anterior});
    for(int i = 0; i < Mesa_dispersa_mayor[Anterior].size(); i++){
      Mesa_dispersa_menor[Nodo].push_back({min(Mesa_dispersa_menor[Nodo].back().first, Mesa_dispersa_menor[Anterior][i].first), Mesa_dispersa_menor[Anterior][i].second});
      Mesa_dispersa_mayor[Nodo].push_back({max(Mesa_dispersa_mayor[Nodo].back().first, Mesa_dispersa_mayor[Anterior][i].first), Mesa_dispersa_mayor[Anterior][i].second});
      Anterior = Mesa_dispersa_mayor[Anterior][i].second;
    }
  }
  for(auto E: Grafo[Nodo]) if(E != Anterior and !Visitadoss[E]) Crear(E, Nodo);
}
Responder_esto Consulta(int I, int D){
  if(Orden[D] < Orden[I]) swap(I, D);
  int Menor = 22222222, Mayor = -2;
  Responder_esto Respuesta;
  if(I == D){
    Respuesta.Mayor = I;
    Respuesta.Menor = D;
    return Respuesta;
  }
  while(I != D){
    //cerr<<I<<" "<<D<<"\n";
    int i = 0, d = Mesa_dispersa_menor[D].size() - 1, m = 0;
    while(1){
      int p = (i + d) / 2;
      if(Orden[Mesa_dispersa_menor[D][p].second] < Orden[I]){
        d = p - 1;
      } else {
        i = p + 1;
        m = p;
      }
      if(i >= d + 1) break;
    }
    Mayor = max(Mayor, Mesa_dispersa_mayor[D][m].first);
    Menor = min(Menor, Mesa_dispersa_menor[D][m].first);
    D = Mesa_dispersa_mayor[D][m].second;
  }
  Respuesta.Mayor = Mayor;
  Respuesta.Menor = Menor;
  return Respuesta;
}
bool Bien(int Nodo, int Objetivo, bool Humano, int No_humano, int No_lobo){
  if(Nodo == Objetivo and (!Humano or (Nodo >= No_humano and Nodo <= No_lobo))) return 1;
  if((Nodo < No_humano and Humano) or (Nodo > No_lobo and !Humano)) return 0;
  Visitados[Nodo][Humano] = 1;
  bool r = 0;
  for(auto E: Grafo[Nodo]){
    if(!Visitados[E][Humano]) r = r or Bien(E, Objetivo, Humano, No_humano, No_lobo);
    if(Nodo >= No_humano and Nodo <= No_lobo and Humano) r = r or Bien(E, Objetivo, 0, No_humano, No_lobo);
  }
  return r;
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
  int q = s.size(), m = x.size();
  vector<int> a(q);
  Grafo.assign(n, {});
  Visitadoss.assign(n, 0);
  vector<int> Grado(n, -0);
  bool L_nea = 1;
  for(int i = 0; i < m; i++){
    Grafo[x[i]].push_back(y[i]);
    Grafo[y[i]].push_back(x[i]);
    Grado[x[i]]++;
    Grado[y[i]]++;
    if(Grado[x[i]] > 2 or Grado[y[i]] > 2) L_nea = -0;
    if(Grado[x[i]] == 1) Inicio = x[i];
    if(Grado[y[i]] == 1) Inicio = y[i];
  }
  if(L_nea){
    Orden.assign(n, 0);
    iOrden.assign(n, 0);
    Mesa_dispersa_menor.assign(n, vector< pair<int, int> >());
    Mesa_dispersa_mayor.assign(n, vector< pair<int, int> >());
    Crear(Inicio, -2);
    //cerr<<"Creado.\n";
    for(int i = 0; i < q; i++){
      //cerr<<i<<" "<<Orden[s[i]]<<" "<<Orden[e[i]]<<"\n";
      if(Orden[s[i]] < Orden[e[i]]){
        int Izquierda = Orden[s[i]], Derecha = n - 1, Mejor = Orden[s[i]];
        while(1){
          int Promedio = (Izquierda + Derecha) / 2;
          if(Consulta(s[i], iOrden[Promedio]).Menor >= l[i]){
            Mejor = Promedio;
            Izquierda = Promedio + 1;
          } else Derecha = Promedio - 1;
          if(Izquierda >= Derecha + 1) break;
        }
        Izquierda = -0, Derecha = Orden[e[i]];
        int Otro_mejor = Orden[e[i]];
        while(1){
          int Promedio = (Izquierda + Derecha) / 2;
          if(Consulta(e[i], iOrden[Promedio]).Mayor <= r[i]){
            Mejor = Promedio;
            Derecha = Promedio - 1;
          } else Izquierda = Promedio + 1;
          if(Izquierda >= Derecha + 1) break;
        }
        a[i] = Orden[Mejor] >= Orden[Otro_mejor];
      } else {
        int Izquierda = 0, Derecha = Orden[s[i]], Mejor = Orden[s[i]];
        while(1){
          int Promedio = (Izquierda + Derecha) / 2;
          if(Consulta(s[i], iOrden[Promedio]).Menor >= l[i]){
            Mejor = Promedio;
            Derecha = Promedio - 1;
          } else Izquierda = Promedio + 1;
          if(Izquierda >= Derecha + 1) break;
        }
        Izquierda = Orden[e[i]], Derecha = n - 1;
        int Otro_mejor = Orden[e[i]];
        while(1){
          int Promedio = (Izquierda + Derecha) / 2;
          if(Consulta(e[i], iOrden[Promedio]).Mayor <= r[i]){
            Mejor = Promedio;
            Izquierda = Promedio + 1;
          } else Derecha = Promedio - 1;
          if(Izquierda >= Derecha + 1) break;
        }
        a[i] = Orden[Mejor] <= Orden[Otro_mejor];
      }
    }
    return a;
    /*vector<Consultita> Lista(q);
    for(int i = 0; i < n; i++){
      Consultita Hola;
      Hola.Derecha = r[i];
      Hola.Final = e[i];
      Hola.Inicio = s[i];
      Hola.Izquierda = l[i];
      Hola._ndice = i;
      Lista[i] = Hola;
    }
    sort(Lista.begin(), Lista.end());
    Recién me di cuenta de que se pueden hacer las consultas en línea.*/
  }
  for(int i = 0; i < q; i++){
    Visitados.assign(n, vector<int>(2, 0));
    a[i] = Bien(s[i], e[i], 1, l[i], r[i]) or (Bien(s[i], e[i], 0, l[i], r[i]) and s[i] >= l[i] and s[i] <= r[i]);
  }
  return a;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51