Submission #1280554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280554		monval	Highway Tolls (IOI18_highway)	C++20	23 / 100	156 ms	34236 KiB

highway

#include "highway.h"

using namespace std;

tuple<vector<int>, vector<vector<int > > > distances(int N, vector<int> neighbors[], vector<int> out_edges[], int u){
  vector<int> distances(N);
  vector<vector<int> > path_edges(N);
  distances[u] = 0;
  int to_reach = N - 1;
  bool reached_past[N];
  bool reached_current[N];
  for(int i = 0; i < N; i++){
    reached_past[i] = false;
    reached_current[i] = false;
  }
  reached_past[u] = true;
  vector<int> current_generation = {u};
  vector<int> next_generation;
  int gen = 0;
  while(to_reach != 0){
    next_generation = {};
    for(auto vertex = current_generation.begin(); vertex != current_generation.end(); vertex++){
      for(int i = 0; i < neighbors[*vertex].size(); i++){
        int neighbor = neighbors[*vertex][i];
        int edge = out_edges[*vertex][i];
        if(!reached_past[neighbor]){
          path_edges[neighbor].push_back(edge);
          if(!reached_current[neighbor]){
            reached_current[neighbor] = true;
            next_generation.push_back(neighbor);
          }
        }
      }
    }
    gen++;
    for(auto vertex = next_generation.begin(); vertex != next_generation.end(); vertex++){
      reached_past[*vertex] = true;
      distances[*vertex] = gen;
    }
    to_reach -= next_generation.size();
    current_generation = next_generation;
  }
  return make_tuple(distances, path_edges);
}

int search_endpoint(int N, int M, int u, vector<int> w, vector<int> distances, vector<vector<int> > path_edges, vector<int> opposing_distances, int distance){
  vector<int> distance_classes[N];
  for(int i = 0; i < N; i++){
    distance_classes[distances[i]].push_back(i);
  }
  vector<int> candidates;
  for(int i = 0; i < N; i++){
    for(auto it = distance_classes[i].begin(); it != distance_classes[i].end(); it++){
      if(opposing_distances[*it] - distances[*it] == 1){
        candidates.push_back(*it);
      }
    }
  }
  vector<int> w_search = w;
  int start = 0;
  int end = candidates.size();
  bool covered = false;
  while(end != start + 1){
    int median = (start + end) / 2;
    if(covered){
      for(int i = start; i < median; i++){
        int vertex = candidates[i];
        for(auto it = path_edges[vertex].begin(); it != path_edges[vertex].end(); it++){
          w_search[*it] = w[*it];
        }
      }
    }else{
      for(int i = median; i < end; i++){
        int vertex = candidates[i];
        for(auto it = path_edges[vertex].begin(); it != path_edges[vertex].end(); it++){
          w_search[*it] = true;
        }
      }
    }
    bool found = ask(w_search) != distance;
    if(found){
      start = median;
    }else{
      end = median;
    }
    covered = found;
  }
  return candidates[start];
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size();
  vector<int> w(M);
  for(int i = 0; i < M; i++){
    w[i] = false;
  }
  long long distance = ask(w);
  int start = 0;
  int end = M;
  while(end != start + 1){
    int median = (start + end) / 2;
    for(int i = start; i < median; i++){
      w[i] ^= true;
    }
    if((ask(w) == distance) ^ w[start]){
      end = median;
    }else{
      start = median;
    }
  }
  w[start] = false;
  int u = U[start];
  int v = V[start];
  vector<int> neighbors[N];
  vector<int> out_edges[N];
  for(int i = 0; i < M; i++){
    neighbors[U[i]].push_back(V[i]);
    neighbors[V[i]].push_back(U[i]);
    out_edges[U[i]].push_back(i);
    out_edges[V[i]].push_back(i);
  }
  vector<int> distances_u;
  vector<vector<int> > path_edges_u;
  vector<int> distances_v;
  vector<vector<int> > path_edges_v;
  tie(distances_u, path_edges_u) = distances(N, neighbors, out_edges, u);
  tie(distances_v, path_edges_v) = distances(N, neighbors, out_edges, v);
  int s = search_endpoint(N, M, u, w, distances_u, path_edges_u, distances_v, distance);
  int t = search_endpoint(N, M, v, w, distances_v, path_edges_v, distances_u, distance);
  answer(s, t);
}

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