Submission #1073801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073801		Gabriel	Highway Tolls (IOI18_highway)	C++17	12 / 100	164 ms	20304 KiB

highway

#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
  int n = N;
  int m = U.size();
  vector<int> a(m, 0);
  int d = (int)(ask(a) / (long long)A);
  set<int> Posibles;
  vector<int> Padres(n, -1);
  Padres[0] = 0;
  vector<bool> Visitados(n, 0);
  Visitados[0] = 1;
  deque<int> Cola;
  vector< vector<int> > Grafo(n);
  map< pair<int, int>, int> Identificador;
  for(int i = 0; i < m; i++){
    Grafo[U[i]].push_back(V[i]);
    Grafo[V[i]].push_back(U[i]);
    Identificador[make_pair(U[i], V[i])] = i;
    Identificador[make_pair(V[i], U[i])] = i;
  }
  Cola.push_back(0);
  vector<int> Distancia(n, INT_MAX);
  Distancia[0] = 0;
  while(!Cola.empty()){
    int Nodo = Cola[0];
    Cola.pop_front();
    Visitados[Nodo] = 1;
    for(auto E: Grafo[Nodo]){
      if(!Visitados[E]){
        Cola.push_back(E);
        Padres[E] = Nodo;
        Distancia[E] = Distancia[Nodo] + 1;
        if(Distancia[E] == d) Posibles.insert(E);
      }
    }
  }
  while(Posibles.size() > 1){
    vector<int> Pregunta(m, 0);
    int i = 0;
    for(auto E: Posibles){
      if(i % 2 == 0){
        Pregunta[Identificador[make_pair(E, Padres[E])]] = 1;
      }
      i++;
    }
    long long D = (long long)d * (long long)A;
    long long DD = ask(Pregunta);
    set<int> Nuevo;
    if(D == DD){
      int i = 0;
      for(auto E: Posibles){
        if(i % 2 == 1){
          Nuevo.insert(E);
        }
        i++;
      }
    } else {
      int i = 0;
      for(auto E: Posibles){
        if(i % 2 == 0){
          Nuevo.insert(E);
        }
        i++;
      }
    }
    Posibles = Nuevo;
  }
  answer(0, *Posibles.begin());
}

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