제출 #1195504

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

highway

#include "highway.h"
#include "bits/stdc++.h"
using namespace std;
long long n, m, a, b;
vector< vector<long long> > Grafo;
vector<int> Consulta;
vector<long long> Anteriores, Distancias;
map< pair<long long, long long>, long long> Identificador;
void DFS(long long Nodo, long long Anterior){
  Anteriores[Nodo] = Anterior;
  Distancias[Nodo] = Distancias[Anterior] + 1;
  for(auto E: Grafo[Nodo]){
    if(E == Anterior) continue;
    DFS(E, Nodo);
  }
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B){
  n = N, m = U.size(), a = A, b = B;
  Grafo.assign(n, {});
  Anteriores.assign(n, 0);
  Distancias.assign(n, -1);
  Consulta.assign(m, 0);
  long long Distancia = ask(Consulta) / a;
  long long j = 0;
  for(long long i = 0; i < m; i++){
    Grafo[U[i]].push_back(V[i]);
    Grafo[V[i]].push_back(U[i]);
    Identificador[{U[i], V[i]}] = j;
    Identificador[{V[i], U[i]}] = j;
    j++;
  }
  DFS(0, 0);
  vector<bool> Sirven(n, 0);
  for(long long i = 0; i < n; i++){
    if(Distancias[i] == Distancia) Sirven[i] = 1;
  }
  while(2 == 2){
    long long c = 0, r;
    for(long long i = 0; i < n; i++){
      if(Sirven[i]){
        c++;
        r = i;
      }
    }
    if(c == 1){
      answer(0, r);
      return;
    }
    c /= 2;
    long long cc = c;
    Consulta = vector<int>(m, 0);
    long long Continuar = 0;
    for(long long i = 0; i < n and cc > 0; i++){
      if(Sirven[i]){
        cc--;
        Consulta[Identificador[{i, Anteriores[i]}]] = 1;
        Continuar = i + 1;
      }
    }
    if(ask(Consulta) == Distancia * a){
      for(long long i = 0; i < n and c > 0; i++){
        if(Sirven[i]){
          c--;
          Sirven[i] = 0;
        }
      }
    } else {
      for(; Continuar < n; Continuar++){
        if(Sirven[Continuar]){
          Sirven[Continuar] = 0;
        }
      }
    }
  }
}

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