제출 #1198491

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198491		Gabriel	Highway Tolls (IOI18_highway)	C++17	51 / 100	1384 ms	327680 KiB

highway

#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
long long n, m, a, b, Distancia, Distanciaa, Distancia_s, Distancia_t;
vector< vector<long long> > Grafo;
map< pair<long long, long long>, long long> Mapa;
map<long long, pair<long long, long long> > Mapa_i;
vector<int> Consulta, Nulo;
vector<long long> Distancia_para_s, Distancia_para_t, Anteriores, Anterioret;
void DFS(long long Nodo, long long Anterior, long long Prohibido, bool S_T){
  if(Nodo != Anterior) Consulta[Mapa[{Anterior, Nodo}]] = 1;
  if(S_T){
    Distancia_para_s[Nodo] = Distancia_para_s[Anterior] + 1;
    Anteriores[Nodo] = Anterior;
  } else {
    Distancia_para_t[Nodo] = Distancia_para_t[Anterior] + 1;
    Anterioret[Nodo] = Anterior;
  }
  for(auto E: Grafo[Nodo]){
    if(E != Anterior and Mapa[{E, Nodo}] != Prohibido){
      Consulta[Mapa[{E, Nodo}]] = 1;
      DFS(E, Nodo, Prohibido, S_T);
    }
  }
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
  n = N;
  m = V.size();
  Grafo.assign(n, {});
  a = A;
  b = B;
  Consulta.assign(m, 0);
  Nulo = Consulta;
  Distancia_para_s.assign(n, -1);
  Distancia_para_t.assign(n, -1);
  Anteriores.assign(n, -1);
  Anterioret.assign(n, -1);
  set<long long> Candidatos;
  for(long long i = 0; i < m; i++){
    Grafo[U[i]].push_back(V[i]);
    Grafo[V[i]].push_back(U[i]);
    Mapa[{U[i], V[i]}] = i;
    Mapa[{V[i], U[i]}] = i;
    Mapa_i[i] = {U[i], V[i]};
    Candidatos.insert(i);
  }
  Distanciaa = ask(Consulta);
  Distancia = Distanciaa / a;
  while(Candidatos.size() > 1){
    Consulta = Nulo;
    vector<long long> Cambiar;
    for(auto E: Candidatos) Cambiar.push_back(E);
    for(long long i = 0; i < Cambiar.size() / 2; i++) Consulta[Cambiar[i]] = 1;
    if(ask(Consulta) > Distanciaa) for(long long i = Cambiar.size() / 2; i < Cambiar.size(); i++) Candidatos.erase(Cambiar[i]);
    else for(long long i = 0; i < Cambiar.size() / 2; i++) Candidatos.erase(Cambiar[i]);
  }
  long long Arista = *Candidatos.begin();
  //cerr<<Mapa_i[Arista].first<<" "<<Mapa_i[Arista].second<<" Arista.\n";
  Consulta = Nulo;
  DFS(Mapa_i[Arista].first, Mapa_i[Arista].first, Arista, 1);
  //Distancia_s = (ask(Consulta) - Distanciaa) / b;
  //for(auto E: Consulta) //cerr<<E<<" ";
  //cerr<<" Consultado.\n";
  //Consulta = Nulo;
  long long Consultita = ask(Consulta);
  DFS(Mapa_i[Arista].second, Mapa_i[Arista].second, Arista, 0);
  //Distancia_t = (ask(Consulta) - Distanciaa) / b;
  Distancia_s = (a * Distancia - Consultita) / (a - b);
  Distancia_t = (Consultita - b * Distancia) / (a - b) - 1;
  /*for(auto E: Consulta) //cerr<<E<<" ";
  //cerr<<" Consulta_de_t.\n";*/
  //cerr<<"Distancias para s: ";
  //for(auto E: Distancia_para_s) //cerr<<E<<" ";
  //cerr<<".\n";
  //cerr<<"Distancias para t: ";
  //for(auto E: Distancia_para_t) //cerr<<E<<" ";
  //cerr<<".\n";
  int s, t;
  //cerr<<Distancia<<" Distancia entre s y t.\n"<<Distanciaa<<" La otra distancia.\n"<<Distancia_s<<" "<<Distancia_t<<" Distancias.\n"<<c<<" Consulta.\n";
  if(Distancia_s == 0) s = Mapa_i[Arista].first;
  else {
    Candidatos.clear();
    for(long long i = 0; i < n; i++) if(Distancia_para_s[i] == Distancia_s) Candidatos.insert(Mapa[{i, Anteriores[i]}]);
    //cerr<<"Candidatos para s:\n";
    //for(auto E: Candidatos) //cerr<<Mapa_i[E].first<<" "<<Mapa_i[E].second<<"\n";
    //cerr<<"\n";
    while(Candidatos.size() > 1){
      Consulta = Nulo;
      vector<long long> Cambiar;
      for(auto E: Candidatos) Cambiar.push_back(E);
      for(long long i = 0; i < Cambiar.size() / 2; i++) Consulta[Cambiar[i]] = 1;
      if(ask(Consulta) > Distanciaa) for(long long i = Cambiar.size() / 2; i < Cambiar.size(); i++) Candidatos.erase(Cambiar[i]);
      else for(long long i = 0; i < Cambiar.size() / 2; i++) Candidatos.erase(Cambiar[i]);
    }
    long long Inicio = Mapa_i[*Candidatos.begin()].first, Final = Mapa_i[*Candidatos.begin()].second;
    if(Distancia_para_s[Inicio] == Distancia_s) s = Inicio;
    else s = Final;
  }
  if(Distancia_t == 0) t = Mapa_i[Arista].second;
  else {
    Candidatos.clear();
    for(long long i = 0; i < n; i++) if(Distancia_para_t[i] == Distancia_t) Candidatos.insert(Mapa[{i, Anterioret[i]}]);
    //cerr<<"Candidatos para t:\n";
    //for(auto E: Candidatos) //cerr<<Mapa_i[E].first<<" "<<Mapa_i[E].second<<"\n";
    //cerr<<"\n";
    while(Candidatos.size() > 1){
      Consulta = Nulo;
      vector<long long> Cambiar;
      for(auto E: Candidatos) Cambiar.push_back(E);
      for(long long i = 0; i < Cambiar.size() / 2; i++) Consulta[Cambiar[i]] = 1;
      if(ask(Consulta) > Distanciaa) for(long long i = Cambiar.size() / 2; i < Cambiar.size(); i++) Candidatos.erase(Cambiar[i]);
      else for(long long i = 0; i < Cambiar.size() / 2; i++) Candidatos.erase(Cambiar[i]);
    }
    long long Inicio = Mapa_i[*Candidatos.begin()].first, Final = Mapa_i[*Candidatos.begin()].second;
    if(Distancia_para_t[Inicio] == Distancia_t) t = Inicio;
    else t = Final;
  }
  //cerr<<s<<" "<<t<<" Estos son.\n";
  answer(s, t);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31